LeetCode 补充题 24. 双栈排序

2023-02-16 HGNULB 约 5 分钟

文章信息 11 个分类 1 个标签

分类

LeetCode CodeTop 中等未解决 5-10 字节跳动美团阿里巴巴猿辅导虾皮高频面试题

题目描述

✅ 补充题 24. 双栈排序

题意分析

给定一个装满整数的栈，要求把它整理成有序状态，过程中只允许再开一个辅助栈，并且两个容器都只能通过压栈、弹栈、看栈顶、判空这几个动作访问。本文采用最常见的约定：整理完成后原栈的栈顶是最小值，越往栈底数值越大。

「只能碰栈顶」是这道题唯一的、也是压倒性的约束。它意味着任何需要按下标随机访问的手段都不可用，任何需要一次看到两个以上元素的比较也不可用——每一步能获得的信息，只有两个栈各自栈顶的那一个数。因此算法必须完全由「搬一个数到另一边」这种原子动作拼出来，而元素的相对顺序只能通过反复倒腾来调整。

「只给一个辅助栈」进一步排除了归并类的思路，因为归并至少需要把数据分成两段各自暂存。剩下能做的，是让辅助栈始终维持一段已整理好的部分，新元素逐个往里插。

边界情形：原栈为空或只有一个元素时，两层循环都不会执行，结果自然正确；出现重复值时不应该产生额外搬运，也不应该破坏顺序；元素总数决定了搬运次数，最坏情况下的搬运量是平方级，题目规模通常不大，可以接受。

解法：辅助栈模拟插入排序

核心思路

只能访问栈顶，又只允许一个辅助栈，最自然的做法是让辅助栈保存“已经排好的一段”，每次把原栈栈顶元素插入到它的正确位置。这本质上是插入排序。

约定最终原栈从栈顶到栈底递增。处理过程中维护不变量：

辅助栈从栈顶到栈底单调递减。

取出待插入值 current 后，只要辅助栈顶大于它，就把这些较大值暂时搬回原栈；直到栈顶不大于 current，再把 current 压入辅助栈。此时新栈顶不小于原栈顶，辅助栈仍保持递减。

原栈清空时，辅助栈已经有序；把它整体倒回原栈会再反转一次，于是原栈栈顶变成最小值。每次插入都保持不变量，最终反转得到目标顺序，因此算法正确。

解题步骤

建立空辅助栈 helper。

从原栈弹出一个元素作为 current。

当 helper 非空且栈顶大于 current 时，把栈顶搬回原栈。

将 current 压入 helper，继续处理原栈。

原栈清空后，把 helper 的全部元素依次压回原栈。

例如待插入 2 时，若辅助栈从栈顶开始是 4, 3, 1，先把 4、3 搬回原栈，再把 2 放到 1 上方；辅助栈变为 2, 1，仍满足递减。后续 3、4 会重新被取出并插回正确位置。

代码实现

import java.util.ArrayDeque;
import java.util.Deque;

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)$，使用题目允许的一个辅助栈；除它以外只需 $O(1)$ 变量。

关键点总结

先和面试官确认“栈顶最小”还是“栈顶最大”，两种目标只差比较方向。

辅助栈的顺序要与最终原栈相反，因为最后一次整体搬运会反转顺序。

内层必须是 while，它完成的是在有序段中的插入，而不是只比较一次。

相等时不回搬，可避免无意义操作，并保持相等元素原有的先后关系。

易错点总结

把 > 写成 <：最终排序方向完全相反。

把内层 while 写成 if：连续多个挡路元素只移走一个，有序不变量被破坏。

原栈清空后忘记把辅助栈倒回：返回容器或栈顶方向不符合题意。

比较前不判空：第一次插入就会访问空栈顶。

借助数组排序：虽然更简单，但违反“只能使用一个辅助栈”的限制。

相似题目

题目	难度	考察点
面试题 03.05. 栈排序	中等	把同一套搬运逻辑封装成支持随时插入的数据结构
155. 最小栈	中等	只需常数时间取最小值，用同步栈而非整体排序
232. 用栈实现队列	简单	同样靠两栈之间的倒腾产生反转，目标是改变出队顺序
225. 用队列实现栈	简单	反向练习，用先进先出容器模拟后进先出
946. 验证栈序列	中等	只做压弹过程的合法性模拟，不涉及元素重排
20. 有效的括号	简单	栈的基础用法，考察配对而非顺序