标签: 深度优先搜索 广度优先搜索 并查集 数组 二分查找 矩阵 堆（优先队列）
难度: Medium
Submission
运行时间: 278 ms
内存: 21.2 MB
class Solution:
def maximumMinimumPath(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]
def exist(val):
vis = [[False] * n for _ in range(m)]
def dfs(x, y):
if x == m - 1 and y == n - 1:
return True
vis[x][y] = True
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if not (0 <= nx < m and 0 <= ny < n) or vis[nx][ny]:
continue
if grid[nx][ny] >= val and dfs(nx, ny):
return True
return False
return dfs(0, 0)
l, r = 0, min(grid[0][0], grid[-1][-1])
while l < r:
mid = (l + r + 1) // 2
if exist(mid):
l = mid
else:
r = mid - 1
return l
Explain
这个题解利用了二分查找和深度优先搜索（DFS）的方法来解决问题。首先，定义了一个辅助函数 exist(val)，该函数通过DFS检查是否可以从网格的左上角(0,0)移动到右下角(m-1,n-1)，同时确保路径上的最小值至少为val。在主函数中，通过二分查找在可能的值域中搜索可以实现这一条件的最大val。这种方法首先设定搜索的范围为两端起点和终点的最小值，然后不断调整搜索范围，直到找到最大的符合条件的val。
时间复杂度: O(m*n*log(min(grid[0][0], grid[-1][-1])))
空间复杂度: O(m*n)
class Solution:
def maximumMinimumPath(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]
def exist(val):
vis = [[False] * n for _ in range(m)] # 创建访问标记数组
def dfs(x, y):
if x == m - 1 and y == n - 1:
return True # 达到右下角，返回成功
vis[x][y] = True # 标记当前点为已访问
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if not (0 <= nx < m and 0 <= ny < n) or vis[nx][ny]:
continue # 检查边界和是否已访问
if grid[nx][ny] >= val and dfs(nx, ny):
return True # 检查值是否符合并递归搜索
return False
return dfs(0, 0)
l, r = 0, min(grid[0][0], grid[-1][-1]) # 初始化二分搜索范围
while l < r:
mid = (l + r + 1) // 2
if exist(mid):
l = mid
else:
r = mid - 1
return l
Explore
在这个问题中，二分查找的目的是寻找可以从网格左上角移动到右下角的路径中，路径上所有点的最小值的最大可能值。选择左上角和右下角的最小值作为初始的`r`值是因为任何成功的路径都必须通过这两个点，因此路径上点的最小值不可能超过这两个点中的最小值。将`l`初始化为0是因为理论上路径点的值可以从0开始。这个范围确保了覆盖所有可能的路径值，因为任何大于右下角和左上角最小值的路径值都不可能构成从起点到终点的有效路径。
`exist(val)`函数的设计目的是检查是否存在从左上角到右下角的路径，使得路径上的所有点的值不小于`val`。一旦找到满足条件的路径，函数就会返回True，并停止进一步搜索。如果在整个递归过程中没有找到符合条件的路径，函数最终返回False。因此，函数在确认找到一个有效路径后会立即停止进一步的搜索，不会探索其他可能的路径。
在二分查找中选择`(l + r + 1) // 2`而不是`(l + r) // 2`主要是为了确保在`l`和`r`非常接近时，`mid`能向上取整，避免出现死循环。具体来说，当`l`和`r`相差1时，如果使用`(l + r) // 2`作为`mid`，则`mid`将始终等于`l`，可能导致二分查找陷入无限循环。使用`(l + r + 1) // 2`可以确保`mid`取到`r`，从而使区间向前推进，这对于找到正确答案是必要的。
在`exist`函数的DFS过程中，对当前点`(x, y)`设置访问标记是为了防止在搜索过程中重复访问同一点，从而避免无限循环。在对一个点进行标记后，只有未被访问的邻接点才会被考虑进一步探索。如果一个邻接点已经被访问，它将不会被再次探索。这种策略减少了重复计算，同时也确保了DFS能够正确地遍历所有可能的路径。每次检查邻接点是否被访问是必要的，因为它决定了是否继续对该方向进行深度搜索。