面试题库 › 算法 / 大模型 › 接雨水问题的三种解法

接雨水问题的三种解法

难度 ★★★在 14 场真实面经中被问到 方向:算法 / 大模型考点:数组与字符串

哪些公司问过

字节跳动7腾讯1快手1华为1百度1携程1大疆1米哈游1

常见岗位:NLP / 语音、C/C++ 软件开发、Go 后端、音视频开发、大模型算法

答案要点

  1. 每个位置的水量 = min(左侧最大高度, 右侧最大高度) - 自身高度(不小于 0)
  2. 动态规划:预处理左右最大高度数组,O(n) 时间、O(n) 空间
  3. 双指针:左右指针向中间,维护两侧最大值,较小一侧先处理,O(n) 时间、O(1) 空间
  4. 单调栈:栈保持递减,遇到更高的柱子弹出栈顶作为凹槽底,按层累加面积
  5. 三种解法时间复杂度都是 O(n)

易错点

面试官常见追问

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

相关面试题