信息技术大学
栈与队列
数据结构与算法·面试高频 · 第 1 章 复杂度与线性结构
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
信息技术大学
栈与队列
数据结构与算法·面试高频 · 第 1 章 复杂度与线性结构
括号匹配类问题
左括号进栈右括号查房：栈顶必须是配偶，一票否决全程。
匹配规则
右括号看栈顶是否为对应的左括号
合法判定
全程无失配，结束时栈恰好为空
变体
最长有效括号：栈存下标，最矮者占栈底
单调栈框架（下一个更大元
栈内保持单调：新元素踢掉所有比它小的，被踢者的答案就是它。
单调递减栈
求下一个更大：小元素被弹出时记答案
环形处理
循环数组遍历两遍，下标对长度取模
复杂度
每元素至多进出栈各一次，均摊 O(n)
队列与栈互相实现
两栈成队列（倒一次汤），两队列成栈（留一个兜底）：考的是结构意识。
两栈队列
压栈进 A，弹栈时 B 为空再把 A 全倒给 B
两队列栈
新元素进空队，另一队依次排到其后
均摊
每个元素至多被倒两次，均摊 O(1)
优先队列与 TopK
TopK 的标配：维护 K 大小的小根堆，堆顶是门槛，新来的比过才换。
小根堆保 K 大
堆顶即第 K 大，新元素胜过堆顶才入堆
复杂度
n 个元素各过一次堆，O(n log k)
变体
第 K 大、频率前 K、合并 K 条有序流
本节要点
- ✓括号匹配：栈顶必须是配偶
- ✓单调栈：被弹出时记答案
- ✓两栈倒汤成队列，均摊 O(1)
- ✓TopK：K 大小的小根堆当门槛
延伸主题：刷每日温度手写两栈队列
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1单调栈为什么是均摊 O(n) 而不是 O(n²)？
参考答案每个元素最多入栈一次、出栈一次，内层弹出的总量受全序列限制；看似嵌套实则线性——与滑动窗口的均摊论证同款。
2最小栈要求 O(1) 取最小值，怎么设计？
参考答案辅助栈与主栈同步压入「到当前为止的最小值」；每个状态都自带最小值快照，弹出时两栈同步弹，min 栈顶即答案。空间换时间的标准姿势。
3求最大的 K 个数，为什么用小根堆而不是大根堆？
参考答案留最小的当守门员：小根堆顶是 K 个里最小的，新元素与它比较即可决定去留；大根堆顶是最大值，没法当门槛。求最小的 K 个则反过来用大根堆。