接雨水 II(LeetCode 407)的思路
哪些公司问过
答案要点
- 最外一圈格子先入最小堆并标记访问,它们构成初始边界
- 每次弹出最矮边界,处理四个未访问邻居,接水量为 max(0, 边界高度-邻居高度)
- 邻居以 max(自身高度, 边界高度) 入堆,作为新的边界
- 正确性来自短板原理:从最低边界扩展,首次访问时水位即被确定
- 时间 O(mn·log(mn)),空间 O(mn);行或列小于 3 时结果为 0
易错点
- 入堆时忘记标记已访问,导致同一格子重复计算水量
- 邻居入堆用了原始高度而不是 max 后的高度,内层水量会算少
- 只扫描行列方向的前后缀最大值,像一维那样处理,结果错误
面试官常见追问
- 为什么一维接雨水的双指针不能直接套到二维?
- 入堆时为什么高度要取 max?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。