LeetCode 面试题 03.05. 栈排序

约 5 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 程序员面试金典（第 6 版） 微软
标签
栈 设计 单调栈

题目描述

✅ 面试题 03.05. 栈排序

image-20260929105721736

题意分析

维护一个最小元素始终位于栈顶的栈，支持 push、pop、peek 和 isEmpty，最多只能使用一个额外的辅助栈。空栈 peek 返回 -1，pop 不做任何操作。

解法：两栈插入排序（维护栈顶最小）

核心思路

[!blue]
每次压入都把新元素插到主栈中的正确位置。 保持主栈从顶到底非递减，辅助栈在一次操作结束时为空。若直接把较大的新值压在栈顶，它会挡住更小元素，因此要先移开主栈顶部所有小于新值的元素。

将这些较小元素逐个弹到辅助栈，直到主栈为空，或当前栈顶已经不小于新值。主栈原本有序，所以停止时剩余的全部元素都不小于新值，此时压入新值，与下方元素的大小关系正确。

再把辅助栈全部倒回。第一次搬运把被移开的元素顺序反转，第二次搬运又恢复它们原来的顺序；它们都比新值小，重新位于新值上方。于是整个主栈再次从顶到底非递减。遇到相等值时可以直接插入，无需把相等元素也搬走。

主栈始终有序且包含全部元素，因此 peek 只读栈顶，pop 只删除栈顶，剩余顺序不会被破坏；isEmpty 也只需查看主栈。这种做法把维护成本集中在插入时，不需要额外排序或其他数据结构。

解题步骤

  1. 建立主栈与辅助栈。
  2. push 时，将主栈中严格小于新值的顶部元素逐个移到辅助栈，直到找到插入位置。
  3. 压入新值，再将辅助栈中的全部元素逐个倒回，恢复它们在新值上方的顺序。
  4. pop 在非空时删除栈顶，peek 在空栈时返回 -1，否则读取栈顶；isEmpty 直接检查主栈。

代码实现

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
}

复杂度分析

  • 时间复杂度：设插入前有 $n$ 个元素，push 最坏需搬出再搬回全部元素，为 $O(n+1)$；连续 $n$ 次插入最坏为 $O(n^2)$。pop、peek、isEmpty 均为 $O(1)$。
  • 空间复杂度：$O(H+1)$，H 为历史最大栈规模，计入主栈与辅助栈保留容量。

关键点总结

[!green]

  • 主栈从顶到底非递减。
  • 辅助栈在一次插入结束后必须清空。
  • 相等元素无需移开，减少重复值的无谓搬运。

易错点总结

[!yellow]

  • 移开的是大于新值的元素：最终会变成栈顶最大。
  • 辅助栈没有全部倒回：查询忽略暂存的合法元素。
  • 空栈 pop 不判断：违反空操作应忽略的要求。
  • 用数组排序或堆替代：不满足只能使用一个辅助栈的限制。

相似题目

题目 难度 关联与区别
补充题 24. 双栈排序 中等 辅助栈有序插入的方法相同，本题需每次push后保持最小值在顶，补充题一次排序已有栈。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/72157872
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！