LeetCode 面试题 03.05. 栈排序
目录
题目描述
题意分析
要设计一个栈，支持
push、pop、peek、isEmpty，但要求栈顶元素始终是当前所有元素中最小的——也就是说peek看到的、pop弹掉的，永远是最小值。栈为空时peek返回-1，pop什么都不做。
约束里最关键的一句是"你只能使用一个额外的临时栈"。这句话同时给了两个信号：其一，不能用数组排序、不能用堆、不能用有序集合，所有中间数据只能倒进那一个辅助栈；其二，既然只有栈可用，唯一能做的重排手段就是"把栈顶一批元素倒到辅助栈、处理完再倒回来"，这本质上就是插入排序——把新元素插到有序序列的正确位置上。
边界上要覆盖：空栈时
pop不能崩溃、peek要返回-1；插入的元素比所有已有元素都小（一个都不用挪）或都大（要挪空整个栈）；存在重复值（stack.peek() < val用严格小于，相等时不再往外挪，保证均摊移动次数不因大量重复值而增加，同时也不影响正确性）。
解法：两栈插入排序（维护栈顶最小）
核心思路
先想暴力：
pop/peek时现场找最小值。找最小值本身要把整个栈倒进辅助栈再倒回来，一次 $O(n)$，而且每次peek都要重做一遍。瓶颈在于查询时才排序，等于每次查询都从零开始，没有把上一次的努力留下来。
反过来想：把代价放在写入侧。如果我们保证"任意时刻主栈
stack从栈顶到栈底是非递减的"，那么peek/pop就只是读/弹栈顶，$O(1)$ 完成。剩下的问题就变成：来了一个新元素val，如何在只用一个辅助栈的前提下，把它塞进这个有序栈的正确位置。
答案就是插入排序的一步。定义不变量：
stack自顶向下非递减（栈顶是最小值），buf在任何一次push结束后都为空。push(val)时：
- 只要
stack栈顶严格小于val，说明这些元素应该排在val前面（更靠近栈顶），把它们逐个弹出暂存到buf。循环停止时，stack栈顶已经 $\ge$val，正是val该待的位置。- 压入
val。- 把
buf里的元素全部倒回stack。因为它们出栈时是"从小到大"依次进入buf的，buf自顶向下就是从大到小；倒回来时按相反顺序进入stack，恰好恢复成自顶向下非递减，并且全部落在val的上方（都比val小）。
两次倒栈让顺序翻转了两遍，等于没翻，只是在中间"插"进了一个元素——这就是为什么这套写法能保持有序。循环条件用
<而不是<=：遇到与val相等的元素时停下，把val压在它上面，结果依然非递减，但少挪了一批元素；如果用<=，一串相同的值会被反复搬来搬去，白白增加常数。
解题步骤
- 构造函数建立主栈
stack和辅助栈buf，都为空。空栈平凡地满足"自顶向下非递减"，不变量从一开始就成立。
push(val)第一步：while (stack 非空 && stack.peek() < val)把栈顶弹进buf。这一步在找val的插入位置。条件里的"栈非空"必须放在前面短路，否则空栈时peek()会崩。用严格小于是为了在相等处提前停下，避免重复值引发无谓搬运。
- 第二步：
stack.push(val)。此刻stack栈顶（若存在）已经 $\ge$val，压上去之后stack自顶向下依然非递减，局部不变量恢复。
- 第三步：
while (buf 非空)把buf全部倒回stack。必须全部倒回，不能留任何元素在buf里过夜——buf里的元素也是栈的合法内容，留在那儿会让peek/isEmpty给出错误答案。倒回后buf重新为空，全局不变量恢复。
pop()：非空才弹栈顶。因为不变量保证栈顶就是最小值，直接弹即可，不需要查找。判空是必须的，题目允许对空栈调用pop。
peek()：空栈返回-1，否则返回栈顶。同样依赖不变量，$O(1)$。
isEmpty()：只判stack是否为空。这一点之所以成立，正是因为不变量保证buf在每次push结束后都是空的——如果允许buf残留元素，这里就必须两个都判。
以
push(1) → push(2) → peek() → pop() → peek()走一遍（栈表示从左到右为栈底到栈顶）：
push(1)：stack为空，while不进入；压入1，stack = [1]；buf为空无需倒回。此时栈顶1。
push(2)：栈顶1 < 2成立，把1弹到buf，stack = []，buf = [1]；stack空，循环结束；压入2，stack = [2]；倒回buf，弹出1压入stack，stack = [2, 1]，buf = []。栈顶是1，自顶向下是1, 2，非递减，不变量成立。
peek()：返回栈顶1，正确（1 是最小值）。
pop()：弹掉1，stack = [2]。
peek()：返回2，正确。再补一段带重复值和"新元素最大"的走查
push(3) → push(1) → push(3)：push(3)后stack = [3]。push(1)：栈顶3 < 1不成立，直接压，stack = [3, 1]，栈顶1。push(3)：栈顶1 < 3成立，1挪到buf；新栈顶3 < 3不成立（严格小于在这里停住），循环结束；压入3，stack = [3, 3]；倒回1，stack = [3, 3, 1]。自顶向下是1, 3, 3，非递减，peek()返回1，正确。注意这里第二个3只搬了一个元素就停下，若条件写成<=则会把栈底的3也搬一趟，做无用功。
代码实现
class SortedStack {
private final Deque<Integer> stack = new ArrayDeque<>();
private final Deque<Integer> buf = new ArrayDeque<>();
public SortedStack() {}
public void push(int val) {
while (!stack.isEmpty() && stack.peek() < val) {
buf.push(stack.pop());
}
stack.push(val);
while (!buf.isEmpty()) {
stack.push(buf.pop());
}
}
public void pop() {
if (!stack.isEmpty()) {
stack.pop();
}
}
public int peek() {
return stack.isEmpty() ? -1 : stack.peek();
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
type SortedStack struct {
stack []int
buf []int
}
func Constructor() SortedStack {
return SortedStack{}
}
func (s *SortedStack) Push(val int) {
for len(s.stack) > 0 && s.stack[len(s.stack)-1] < val {
s.buf = append(s.buf, s.stack[len(s.stack)-1])
s.stack = s.stack[:len(s.stack)-1]
}
s.stack = append(s.stack, val)
for len(s.buf) > 0 {
s.stack = append(s.stack, s.buf[len(s.buf)-1])
s.buf = s.buf[:len(s.buf)-1]
}
}
func (s *SortedStack) Pop() {
if len(s.stack) == 0 {
return
}
s.stack = s.stack[:len(s.stack)-1]
}
func (s *SortedStack) Peek() int {
if len(s.stack) == 0 {
return -1
}
return s.stack[len(s.stack)-1]
}
func (s *SortedStack) IsEmpty() bool {
return len(s.stack) == 0
}
复杂度分析
- 时间复杂度：
push最坏 $O(n)$——新元素比所有已有元素都大时，要把整栈挪到buf再挪回来，共 $2n$ 次栈操作；pop、peek、isEmpty都是 $O(1)$，因为不变量已经把最小值放在栈顶。n次push最坏总代价 $O(n^2)$，与插入排序同阶，这也是"只许用一个辅助栈"这个约束下的必然代价。- 空间复杂度：$O(n)$，
n为栈中元素个数。主栈存全部元素，辅助栈buf只在单次push期间临时占用，最坏也是 $O(n)$，但两者不会同时装满：任意时刻两个栈的元素总数恰好等于当前元素个数加一。
关键点总结
- "查询要 $O(1)$"就把代价挪到写入侧。这是所有带极值查询的设计题的第一反应：先问"能不能让容器始终保持某种有序性"，如果能，查询就退化成读一个固定位置。
- 只有一个辅助栈时，唯一的重排原语是"倒出去再倒回来"。倒两次等于不变序，中间插入一个元素就完成了插入排序的一步。认清这一点，就不会去纠结"能不能更快"——在这个约束下 $O(n)$ 的
push已是最优。- 辅助结构必须在每次操作结束时清空。
buf里如果残留元素，isEmpty、peek全都会给出错误答案。凡是用到临时容器的设计题，都要把"操作结束时临时容器为空"写进不变量。- 比较用严格小于还是小于等于，决定的是常数而不是正确性。这里两种写法答案都对，但
<能让一串相同值免于反复搬运。面试里能主动说清"为什么我选严格小于"是加分项。- 面试视角：先问清"排序方向"和"辅助空间限制"。有的版本要求栈顶最大，有的允许用多个辅助栈甚至递归。开口前确认这两点，能避免写完被推翻；若面试官放宽到"可用任意结构"，则直接答"用有序链表或跳表可把
push降到 $O(\log n)$"。
易错点总结
- 错误写法：
while (stack.peek() < val)没有先判空 → 用例第一次push(1)：对空栈调peek()，Java 的ArrayDeque.peek()返回null导致拆箱 NPE，Go 里是下标-1越界 panic。短路判空必须写在比较前面。- 错误写法：
while (stack.peek() > val)（比较方向反了） → 用例push(1), push(2), peek()：1 > 2不成立直接压入，stack = [1, 2]，栈顶是2，peek()返回2，正确答案是1。- 错误写法：
push结束后忘了把buf倒回stack→ 用例push(1), push(2), peek()：1留在buf里，stack = [2]，peek()返回2而不是1；更严重的是isEmpty()在把2也弹掉后会返回true，而1还在buf里，元素凭空消失。- 错误写法：
isEmpty()写成return stack.isEmpty() && buf.isEmpty()但push里确实会残留 → 这是在用判空去掩盖上一条 bug：用例push(1), push(2), pop(), peek()依然会返回错误的值。正确做法是修好push，而不是让判空去迁就残留。- 错误写法：
pop()不判空直接stack.pop()→ 用例：新建对象后立刻pop()：Java 抛NoSuchElementException，Go 切片越界 panic。题目明确允许对空栈调用pop，必须静默返回。- 错误写法：
peek()空栈时返回0或Integer.MIN_VALUE→ 用例：新建对象后peek()：期望-1，返回其他值直接 WA。题目对空栈的返回值有明确规定，不能自行选哨兵。- 错误写法：把
pop()写成有返回值并返回stack.pop()→ 与题目签名不符，Java 会编译报错；即使强行改签名，判题也会因为方法签名不匹配而失败。设计题必须逐字对齐给定的接口。- 错误写法：Go 里搬运时写成
s.buf = append(s.buf, s.stack...)再清空s.stack→ 用例push(3), push(1), push(2)：这是把整个主栈无条件搬走，而不是只搬比val小的那一段；2会被压到栈底，倒回后自顶向下变成1, 3, 2，不再非递减，后续pop顺序全错。- 错误写法：Go 里
Push用值接收者 → 用例push(1), isEmpty()：修改的是副本，主对象始终为空，isEmpty()返回true。- 错误写法：为了"优化"而在
push里只挪一半、剩下的留到pop时再处理 → 用例push(3), push(1), push(2), peek()：不变量被破坏后，peek读到的栈顶不再保证是最小值，返回2而不是1。不变量要么全程维持，要么就换一套设计，不能"部分维持"。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 面试题 03.02. 栈的最小值 | 简单 | 只要求 $O(1)$ 查最小值而不要求整体有序，辅助栈只存极值历史 |
| 155. 最小栈 | 中等 | 同上模型的主站版本，追问方向是 $O(1)$ 额外空间的存差值写法 |
| 面试题 03.03. 堆盘子 | 中等 | 同样是栈的设计题，难点在容量分摞与中间掏空后的下标语义 |
| 147. 对链表进行插入排序 | 中等 | 同样是插入排序，但载体是链表，靠改指针而不是倒容器完成插入 |
| 剑指 Offer 31. 栈的压入、弹出序列 | 中等 | 用辅助栈模拟给定操作序列并校验合法性，不涉及维持有序性 |