柱状图中最大的矩形(LC84,单调栈)
哪些公司问过
答案要点
- 枚举每根柱子为高,向左右延伸到第一个更矮的柱子
- 维护高度递增的单调栈,栈中存下标
- 当前柱子更矮时弹出栈顶并计算面积,宽度 = i − 新栈顶 − 1,栈空时为 i
- 遍历结束后剩余柱子的右边界为 n,可用首尾高度 0 的哨兵简化
- 每根柱子进出栈一次,时间空间 O(n)
易错点
- 宽度用 i − 栈顶下标计算,没减一或没用新栈顶
- 遍历结束忘记处理栈中剩余柱子
- 栈中存高度而不是下标,无法计算宽度
面试官常见追问
- LC85 最大矩形怎么转化?
- 相等高度的柱子会不会算错?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 栈和队列的区别与应用68 场
- 四则运算表达式求值15 场
- 循环队列(环形缓冲区)的实现14 场
- 最长有效括号12 场
- 滑动窗口最大值与滑动平均滤波12 场
- 有效的括号(栈)11 场
- 实现支持 O(1) 获取最小值的栈9 场
- 单调栈:下一个更大元素与每日温度6 场
- 数据流的中位数(大根堆加小根堆)5 场
- 滑动窗口最大值的单调队列解法4 场