单调栈典型题:下一个更大元素
哪些公司问过
答案要点
- 栈内保持单调(递增或递减),通常存下标便于回填答案和计算距离
- 求下一个更大元素:维护递减栈,当前元素大于栈顶时弹栈并记录答案
- 每个元素最多进出栈一次,时间 O(n),空间 O(n)
- 循环数组遍历 2n 次并对下标取模;结束时仍在栈中的元素答案为 −1
- 典型题:每日温度、柱状图中最大矩形、接雨水
易错点
- 栈里存值而不是下标,导致无法回填答案或计算距离
- 弹栈条件的严格与非严格写错,相等元素处理出错
- 看到嵌套循环就以为是 O(n²),其实均摊 O(n)
面试官常见追问
- 柱状图中最大矩形怎么用单调栈?
- 相等元素怎么处理?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 栈和队列的区别与应用68 场
- 四则运算表达式求值15 场
- 循环队列(环形缓冲区)的实现14 场
- 最长有效括号12 场
- 滑动窗口最大值与滑动平均滤波12 场
- 有效的括号(栈)11 场
- 实现支持 O(1) 获取最小值的栈9 场
- 单调栈:下一个更大元素与每日温度6 场
- 数据流的中位数(大根堆加小根堆)5 场
- 滑动窗口最大值的单调队列解法4 场