栈与队列

一句话：栈解决”最近的还没处理完”（括号匹配、表达式求值、函数调用），队列解决”先来的先处理”（层序遍历、BFS）。单调栈/单调队列是在此之上加了一条淘汰规则——不是谁都留在栈/队列里，而是只留下”未来还可能有用”的那些。

普通栈：处理有嵌套结构的问题

20-有效的括号、394-字符串解码、150-逆波兰表达式求值 的共性是输入天然带嵌套/依赖关系，必须先处理完里层才能处理外层。栈的 LIFO 特性恰好和这种”最近展开的最先收尾”的结构对应——遇到左括号/操作数就压栈，遇到右括号/操作符就弹栈处理，弹出的顺序自动就是”由内到外”。

155-最小栈（O(1) 获取最小值）的技巧是辅助栈同步维护当前最小值：主栈每压入一个元素，辅助栈同步压入”到目前为止的最小值”，两个栈永远等长，出栈时同步弹出即可——用空间换掉了”重新扫描找最小值”的时间。

232-用栈实现队列 / 225-用队列实现栈 是同一个思想的两个方向：用两个同类结构模拟另一类结构的行为，核心都是”倒一次序”——两个栈互倒可以把 LIFO 变成 FIFO；两个队列配合可以让新元素排到队首模拟 LIFO。

单调栈/单调队列：栈/队列 + 淘汰规则

单调栈（739-每日温度、84-柱状图中最大矩形、496/503-下一个更大元素）回答的是同一类问题：对每个元素，找左边或右边第一个比它大（或小）的元素。

关键洞察：如果新来的元素比栈顶大，栈顶就再也不可能是”谁的下一个更大元素”了（因为新元素本身更近且更大），可以永久扔掉——这就是”淘汰规则”的含义。淘汰掉的同时，正好可以顺手结算被淘汰者的答案（谁淘汰了它，谁就是它的”下一个更大元素”）。全程每个元素只入栈出栈一次，所以是 O(n) 而不是暴力的 O(n²)。

单调队列（239-滑动窗口最大值）是单调栈的滑动窗口版：窗口每滑动一步，从队尾淘汰所有比新元素小的旧元素（同样的道理——它们不可能再是最大值），再检查队首是否已经滑出窗口范围。队列维护的是”候选最大值的递减序列”，队首永远是当前窗口的最大值。

易错点：淘汰的方向决定找的是”大”还是”小”

写单调栈时最容易搞反的是淘汰条件的方向：要找”下一个更大元素”，就要在新元素比栈顶大时淘汰栈顶（维护一个递减栈）；要找”下一个更小元素”，方向整个反过来。写代码前先想清楚”我要维护的栈是递增还是递减”，再决定 while 循环里的比较符号，而不是凭直觉试错。