Given an m x n integer matrix grid, return the maximum score of a path starting at (0, 0) and ending at (m - 1, n - 1) moving in the 4 cardinal directions.
The score of a path is the minimum value in that path.
8 → 4 → 5 → 9 is 4.Example 1:
Input: grid = [[5,4,5],[1,2,6],[7,4,6]] Output: 4 Explanation: The path with the maximum score is highlighted in yellow.
Example 2:
Input: grid = [[2,2,1,2,2,2],[1,2,2,2,1,2]] Output: 2
Example 3:
Input: grid = [[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]] Output: 3dfs approach
def maximumMinimumPath(grid): R, C = len(grid), len(grid[0]) max_min_val = 0 visited = [[False for _ in range(C)] for _ in range(R)] def dfs(r, c, current_min): nonlocal max_min_val # Update the minimum value seen on THIS specific path current_min = min(current_min, grid[r][c]) # Pruning: If our current path is already worse than the best # path we've found so far, stop exploring it. if current_min <= max_min_val: return # If we reached the goal, update our global best if r == R - 1 and c == C - 1: max_min_val = max(max_min_val, current_min) return visited[r][c] = True # Explore neighbors for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]: nr, nc = r + dr, c + dc if 0 <= nr < R and 0 <= nc < C and not visited[nr][nc]: dfs(nr, nc, current_min) # Backtrack: Unmark visited so other paths can use this cell visited[r][c] = False dfs(0, 0, grid[0][0]) return max_min_val
better approach
To solve the Path With Maximum Minimum Value problem (LeetCode 1102), the goal is to find a path from $(0, 0)$ to $(R-1, C-1)$ such that the minimum value encountered along the path is as large as possible.
This is a classic variation of a shortest path problem, but instead of minimizing the sum, we are maximizing the bottleneck.
We use a Max-Priority Queue (Max-Heap) to always explore the cell with the highest value currently available to us. By greedily picking the highest value neighbor, the first time we reach the destination, the "minimum value seen so far" is guaranteed to be the maximum possible minimum for any path.
1 import heapq 2 3 def maximumMinimumPath(grid): 4 R, C = len(grid), len(grid[0]) 5 6 # Max-heap stores (-value, row, col) 7 # We start at (0, 0) 8 max_heap = [(-grid[0][0], 0, 0)] 9 10 # Keep track of the minimum value encountered on our current best path 11 res = grid[0][0] 12 13 visited = [[False for _ in range(C)] for _ in range(R)] 14 visited[0][0] = True 15 16 while max_heap: 17 val, r, c = heapq.heappop(max_heap) 18 val = -val # Convert back to positive 19 20 # The bottleneck of the path is the minimum value we've seen 21 res = min(res, val) 22 23 # If we reached the goal, this is the maximum possible bottleneck 24 if r == R - 1 and c == C - 1: 25 return res 26 27 # Explore 4-directional neighbors 28 for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]: 29 nr, nc = r + dr, c + dc 30 31 if 0 <= nr < R and 0 <= nc < C and not visited[nr][nc]: 32 visited[nr][nc] = True 33 heapq.heappush(max_heap, (-grid[nr][nc], nr, nc)) 34 35 return res
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。