Uber Phone Screen 网格阈值查询：从左上角可得多少分

题目重点：每个阈值只可进入值严格更小的四邻格，首次访问得一分；从逐查询 BFS 推到按阈值排序、最小堆扩张的离线解。

题意与假设

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

进入数值≥limit 的格子即不能继续得分或扩张；因此答案是从 (0,0) 通过所有值严格小于 limit 的格子可达的不同格子数。允许重复走格子，但重复不加分。
terrain 为矩形整数网格，可能有负值；空网格答案全 0，非矩形输入报错。limit 数组可以重复、无序。
题目写‘碰到不合格格后过程结束’，本文按可选择移动路径且取最大分解释：不必主动踏入阻塞格，可遍历整个可达分量；若面试官要求某种强制行走策略，则答案不同。

解题路线

基线：对每个 limit，从左上角做一次 BFS，只把值<limit 的四邻格入队，visited 避免重复计分；复杂度 O(kmn)。这是独立验证 oracle，也能在查询很少时直接使用。
优化：把查询按阈值升序排序，答案放回原下标。最小堆存已发现但尚未激活的边界格，按该格值排序；最初只放 (0,0)。
处理阈值 q 时，持续弹出堆顶值<q 的格，累计一个新可达格，再把尚未发现的四邻格入堆。堆顶≥q 时停止，当前累计数就是这一阈值的可达分量大小。下一更大阈值从同一堆接着扩张。
不变量：堆包含可达分量邻接的全部尚未激活边界，堆顶是其中最小值。若堆顶都不合格，任何边界都不能跨越；若合格，弹出后该格从已有可达格可达，扩张安全。每格仅入堆一次。

手动走一遍

terrain=[[1,4],[2,3]]：limit=2 仅左上角 1 可达，答案 1；limit=4 能走 1→2→3，答案 3，右上角 4 因为要求严格小于 4 不计；limit=5 四格均可达，答案 4。题目尾部的排版样例不作为这里的验证依据。

Python 参考实现

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

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

"""Offline threshold queries for cells reachable from (0, 0)."""

import heapq


def max_points(terrain: list[list[int]], limits: list[int]) -> list[int]:
    if not terrain or not terrain[0]:
        return [0] * len(limits)
    rows, cols = len(terrain), len(terrain[0])
    if any(len(row) != cols for row in terrain):
        raise ValueError("terrain must be rectangular")

    answer = [0] * len(limits)
    seen = {(0, 0)}
    frontier = [(terrain[0][0], 0, 0)]
    reached = 0
    for limit, query_index in sorted((limit, i) for i, limit in enumerate(limits)):
        while frontier and frontier[0][0] < limit:
            _, row, col = heapq.heappop(frontier)
            reached += 1
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = row + dr, col + dc
                if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in seen:
                    seen.add((nr, nc))
                    heapq.heappush(frontier, (terrain[nr][nc], nr, nc))
        answer[query_index] = reached
    return answer

复杂度

N=mn 个格、k 个查询：查询排序 O(k log k)，每格至多入堆/出堆一次，最坏 O(N log N+k log k) 时间；seen 与堆 O(N)，答案 O(k)。逐查询 BFS 是 O(kN) 时间、O(N) 空间。

易错点与追问

容易失分的边界

用≤limit 而非严格小于，会把等于阈值的边界格误计。
认为只需统计全网格数值小于阈值的格子，忽略可能被高值屏障与左上角隔断。
在格子首次发现入堆时就计分；此时它可能高于当前阈值，只有弹出并满足条件才可计分。
按排序后的查询顺序直接输出，忘记保存原下标；重复阈值也需要各自答案。

继续深挖

若阈值查询在线乱序到达，不能复用单调堆状态；可对所有格按值离线建 DSU 与分量大小查询，但仍需阈值预处理。
若网格值会动态修改，离线单调扩张不再适用，需重新评估每次 BFS 与批量重建。
若允许八邻而非四邻，只改邻居枚举；可达分量及复杂度不变。