Google 网格最小化最大高度：Dijkstra 为什么成立

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 网格非空且为矩形，从左上到右下，只能上下左右移动；每个格子的值是进入该格所需的最低水位。
• 一条路径的代价是这条路径经过的所有格子中的最大高度，包含起点与终点。目标是最小化这个最大值。
• 若题面加入障碍，需在扩展邻居时跳过；本文代码按全部格子可通行实现。

解题路线

1. 令 best[r][c] 表示走到该格子时可能达到的最小“路径最高高度”。起点的值就是自身高度。
2. 从当前格走到邻格时，新的路径代价是 max(当前代价, 邻格高度)，若更小就更新并入最小堆。
3. 该代价沿路径不会下降，因此每次弹出的最小未确定状态已经最优。第一次弹出终点即可返回。

手动走一遍

例如网格 [[0,2],[1,3]]：走右再下的最高高度为 3，走下再右也是 3，结果为 3。若把右下角改为 1，走下再右的最高高度变成 1，而走右再下仍为 2，算法返回 1。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from heapq import heappop, heappush


def minimum_maximum_height(heights):
    """Minimize the largest cell height on a four-direction grid path."""
    if not heights or not heights[0]:
        raise ValueError("grid must be nonempty")
    rows, cols = len(heights), len(heights[0])
    if any(len(row) != cols for row in heights):
        raise ValueError("grid must be rectangular")

    infinity = float("inf")
    best = [[infinity] * cols for _ in range(rows)]
    best[0][0] = heights[0][0]
    heap = [(best[0][0], 0, 0)]

    while heap:
        cost, row, col = heappop(heap)
        if cost != best[row][col]:
            continue
        if (row, col) == (rows - 1, cols - 1):
            return cost
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = row + dr, col + dc
            if not (0 <= nr < rows and 0 <= nc < cols):
                continue
            candidate = max(cost, heights[nr][nc])
            if candidate < best[nr][nc]:
                best[nr][nc] = candidate
                heappush(heap, (candidate, nr, nc))

    raise ValueError("target is unreachable")

复杂度

设网格有 R×C 个格子，每格最多检查四条边；堆实现的时间为 O(RC log(RC))，best 与堆的空间为 O(RC)。也可以二分高度阈值，并用 BFS 判断该阈值下能否连通。

易错点与追问

容易失分的边界

• 把松弛公式误写成当前代价加邻格高度，就求成了路径和；写成相邻格高度差则变成另一道题。
• 起点高度也应纳入路径最大值；重复入堆的旧状态需要用 best 判定后跳过。
• 当面试官追问普通带权图最短路时，代价又改回路径权重之和，不能沿用 max 松弛。

继续深挖

• 二分答案的可行性具有单调性：阈值提高只会增加可进入格子。解释这一点比背二分模板更重要。
• 若要求输出具体路线，更新 best 时记录前驱，终点确定后反向还原路径。