单调栈题解：栈里存的不是元素，是还没等到答案的位置

单调栈题解栈里存的不是元素是还没等到答案的位置单调栈是高频题但很多人背模板背得很痛苦。其实单调栈的核心很简单栈里存的不是普通元素而是“还没等到答案的位置”。每来一个新元素就看看它能不能帮栈顶那些位置结算答案。一旦理解“等待答案”这件事下一更大元素、每日温度、柱状图最大矩形都会清楚很多。一、从每日温度理解题目给定每天温度求每一天还要等几天才有更高温度。我们维护一个温度递减的栈里面存下标。flowchart TD A[遍历当前温度] -- B{当前温度是否大于栈顶} B --|是| C[弹出栈顶并结算等待天数] C -- B B --|否| D[当前下标入栈]栈里的人都在等一个更高温度。当前温度来了能帮谁解答就把谁弹出去。二、代码实现def dailyTemperatures(temperatures): ans [0] * len(temperatures) stack [] for i, t in enumerate(temperatures): while stack and t temperatures[stack[-1]]: j stack.pop() ans[j] i - j stack.append(i) return ans注意栈里存下标不是温度。因为答案需要距离必须知道位置。三、复杂度证明每个下标最多入栈一次、出栈一次所以总操作数是 O(n)。while 看起来嵌套在 for 里但不是 O(n²)。这是单调栈最重要的复杂度证明。入栈次数 n 出栈次数 n 总复杂度 O(n)面试时能把这句话讲清楚比只写模板更重要。四、常见边界递减数组会全部留在栈里答案全 0递增数组会每次弹出前一个相等温度不算更高所以条件是不是。很多错解就错在相等处理。题目问“更高”不是“更高或相等”。再看柱状图最大矩形单调栈里等的就不是“更大元素”而是“右边第一个更小元素”。每个柱子需要知道它能向左右扩展多远。def largestRectangleArea(heights): stack [] ans 0 for i, h in enumerate(heights [0]): while stack and h heights[stack[-1]]: height heights[stack.pop()] left stack[-1] if stack else -1 ans max(ans, height * (i - left - 1)) stack.append(i) return ans这里末尾加 0 是为了把栈里剩余柱子全部结算。这个技巧不是魔法是人为制造一个最小右边界。单调栈题最值得练的是识别“谁在等什么答案”。等更大、等更小、等边界代码形态会变但思想一致。面试表达时可以这样讲我维护一个单调栈栈内元素还没有找到右侧第一个更大值当前元素如果更大就不断弹栈并结算答案。每个元素最多进出栈一次所以 O(n)。这段话比“我用模板”强多了。proof_line: invariant: 栈内下标对应值单调递减 settlement: 当前值为被弹元素的第一个更大值 complexity: 每个下标进栈出栈各一次会写也要会讲。算法题面试讲清不变量很加分。五、总结单调栈里存的是还没等到答案的位置。新元素到来时它负责结算能结算的人。每个元素入栈一次、出栈一次所以复杂度 O(n)。别死背模板。先问谁在等答案谁能帮它结算