面试题库 › 嵌入式 › 柱状图中最大的矩形(LC84,单调栈)

柱状图中最大的矩形(LC84,单调栈)

难度 ★★★在 1 场真实面经中被问到 方向:嵌入式考点:栈与队列

哪些公司问过

大疆1

常见岗位:嵌入式软件

答案要点

  1. 枚举每根柱子为高,向左右延伸到第一个更矮的柱子
  2. 维护高度递增的单调栈,栈中存下标
  3. 当前柱子更矮时弹出栈顶并计算面积,宽度 = i − 新栈顶 − 1,栈空时为 i
  4. 遍历结束后剩余柱子的右边界为 n,可用首尾高度 0 的哨兵简化
  5. 每根柱子进出栈一次,时间空间 O(n)

易错点

面试官常见追问

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

相关面试题