LeetCode 补充题 24. 双栈排序
题目描述
:::fold-green 相关原题
两题都要求最小元素位于栈顶，并且只能使用一个辅助栈。LeetCode 原题要求实现支持增删查询的栈；本文对已有栈执行一次排序。
:::
给定一个栈
stack，请只借助另一个辅助栈进行排序，使原栈从栈顶到栈底按非递减顺序排列，即最小元素位于栈顶。排序后保留所有元素及其出现次数，结果仍存放在原栈中。可以使用常数个临时变量，但不能将全部元素转移到数组或列表中调用排序函数。
示例 1：
输入：stack = [3,1,2]（按栈顶到栈底列出）
输出：[1,2,3]（按栈顶到栈底列出）
示例 2：
输入：stack = [2,1,2]（按栈顶到栈底列出）
输出：[1,2,2]（按栈顶到栈底列出）
提示：
- 排序后最小元素位于栈顶，允许重复值和空栈。
- 只通过压栈、弹栈和查看栈顶等栈操作搬移元素。
- 示例按逻辑栈顺序展示；Go 实现用切片末尾表示栈顶，因此其底层切片顺序与示例的展示方向相反。
题意分析
给定一个栈，只借助另一个辅助栈，将元素整理成栈顶最小、从顶到底非递减的顺序。重复元素都需要保留，最终结果仍放回原栈。
只能使用压栈、弹栈和查看栈顶等操作，不能把全部元素转到数组后直接排序。Java 代码用
Deque的栈接口；Go 代码用切片末尾表示栈顶，返回整理后的切片。
解法：辅助栈模拟插入排序
核心思路
[!blue]
可以像插入排序一样，每次把原栈弹出的值放入辅助栈的合适位置。由于只能访问顶部，先让辅助栈保持“栈顶最大、从顶到底非递增”，这样大值可以通过弹栈临时移开，为当前较小值让出位置。
取出
current后，只要辅助栈顶大于它，就把栈顶移回原栈。停止时，辅助栈为空，或者顶部已经不大于current；更下面的值也不会更大，因此把current压在顶部后，辅助栈仍然有序。暂时搬回原栈的元素没有丢弃，会在后续循环中继续处理。它们原本从大到小被移出，叠到原栈后会从小到大重新弹出；这些值都大于刚插入的
current，能够依次直接压回辅助栈，不会在这段恢复过程中反复互相搬动。于是每处理一个原始待插入元素，都能完成一次有限的有序插入。等原栈为空，所有元素都在辅助栈中，顺序为顶部最大。再把辅助栈逐个弹回原栈，整个顺序反转一次，原栈就变成顶部最小。相等值无需移开，使用严格大于比较即可保留它们。
解题步骤
- 创建空辅助栈，只要原栈还有元素，就弹出一个当前值。
- 辅助栈非空且栈顶更大时，将其顶部连续移回原栈。
- 将当前值压入辅助栈，继续从原栈取值；刚搬回的元素也会按栈顺序被重新处理。
- 原栈清空后，将辅助栈全部倒回原栈。
- 返回原栈，此时连续弹出元素即可得到从小到大的次序。空栈和单元素栈也自然适用。
代码实现
class Solution {
public Deque<Integer> sortStack(Deque<Integer> stack) {
Deque<Integer> helper = new ArrayDeque<>();
while (!stack.isEmpty()) {
int current = stack.pop();
// 先移走挡路的大值，插入后辅助栈仍保持栈顶较大
while (!helper.isEmpty() && helper.peek() > current) {
stack.push(helper.pop());
}
helper.push(current);
}
// 整体倒回再反转一次，原栈栈顶变成最小
while (!helper.isEmpty()) {
stack.push(helper.pop());
}
return stack;
}
}
func sortStack(stack []int) []int {
helper := make([]int, 0, len(stack))
for len(stack) > 0 {
current := stack[len(stack)-1]
stack = stack[:len(stack)-1]
// 先移走挡路的大值，插入后辅助栈仍保持栈顶较大
for len(helper) > 0 && helper[len(helper)-1] > current {
stack = append(stack, helper[len(helper)-1])
helper = helper[:len(helper)-1]
}
helper = append(helper, current)
}
// 整体倒回再反转一次，原栈栈顶变成最小
for len(helper) > 0 {
stack = append(stack, helper[len(helper)-1])
helper = helper[:len(helper)-1]
}
return stack
}
复杂度分析
- 时间复杂度：最坏 $O(n^2)$。一次有序插入最多移开并放回此前的线性数量元素，全部插入的搬移总量为平方级；若无需回搬，则为 $O(n)$。
- 空间复杂度：$O(n)$，只使用一个最多容纳全部元素的辅助栈，当前值等标量为常数空间。
关键点总结
[!green]
- 辅助栈先保持顶部较大，便于通过顶部搬移实现有序插入。
- 临时搬回的元素继续参与处理，不是已经被丢弃或永久排好位置。
- 最后一次整体倒栈反转顺序，使原栈顶部最小。
- 严格大于才搬移，相等值直接保留，避免无意义的循环交换。
易错点总结
[!yellow]
- 比较方向写反，却仍按原方式倒回，会得到顶部最大的相反顺序。
- 把搬移条件写成大于等于，相等元素可能不断被移回、重新取出，再彼此替换，无法结束。
- 只移开一个更大元素，辅助栈中还可能有更多阻挡当前值的元素，插入后不再有序。
- 用原栈最初的长度限制外层循环，忽略临时搬回的元素还需要重新处理。
- 忘记最后整体倒回，排序后的元素仍在辅助栈中，原栈为空。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 面试题 03.05. 栈排序 | 中等 | 辅助栈有序插入可复用，原题每次push后保持栈顶最小，本题一次整理已有栈。 |
| 147. 对链表进行插入排序 | 中等 | 同样逐个插入已排序部分，链表可直接定位前驱，本题只能用辅助栈临时搬开元素。 |