面试题库 › Java 后端 › 接雨水 II(LeetCode 407)的思路

接雨水 II(LeetCode 407)的思路

难度 ★★★在 3 场真实面经中被问到 方向:Java 后端考点:TopK与海量数据

哪些公司问过

腾讯2字节跳动1

常见岗位:Java 后端、AI 应用 / Agent 开发

答案要点

  1. 最外一圈格子先入最小堆并标记访问,它们构成初始边界
  2. 每次弹出最矮边界,处理四个未访问邻居,接水量为 max(0, 边界高度-邻居高度)
  3. 邻居以 max(自身高度, 边界高度) 入堆,作为新的边界
  4. 正确性来自短板原理:从最低边界扩展,首次访问时水位即被确定
  5. 时间 O(mn·log(mn)),空间 O(mn);行或列小于 3 时结果为 0

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题