LeetCode 剑指 Offer 30. 包含min函数的栈

约 5 分钟
文章信息 8 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 剑指 Offer 剑指 Offer（第 2 版） 字节
标签
栈 设计

题目描述

✅ 剑指 Offer 30. 包含min函数的栈

image-20261001230752553

image-20260928194353087

image-20260928194353088

题意分析

实现支持入栈、出栈、读取栈顶和读取当前最小值的栈。min 只查询，不删除元素；题目保证弹出和查询时栈非空，元素值允许重复。

最小值不能每次通过遍历重新寻找。除了记录当前最小值，还需要在它被弹出后恢复之前的最小值，所以要保存最小值变化的历史。

解法：辅助最小栈

核心思路

[!blue]

数据栈 data 保存全部元素，辅助栈 mins 只保存成为最小值的那些出现。压入新值时，如果辅助栈为空，或新值不大于当前最小值，就同时压入辅助栈；否则只压入数据栈。

较大的新值为什么不需要记录？它压在旧最小值上面，按照栈的顺序，必须先弹出它才能弹出下面的旧最小值，所以在它还留在栈里时，不会需要它来替代那个更小值。只有更小或相等的新值会影响最小值的恢复过程。

相等值也必须分别记录。这样多个相同最小值各对应一次出现，弹出其中一个时辅助栈只减少一份，其余相同最小值仍有记录，不会过早恢复成更大的历史值。

出栈时先保存数据栈实际弹出的值。若它等于当前最小值，辅助栈也弹出一次，露出此前应恢复的最小值；否则最小元素仍在数据栈中，辅助栈保持不变。因此两个栈不要求等高，但辅助栈顶始终准确表示当前最小值。

top 读取数据栈顶，min 读取辅助栈顶，都不修改状态。Java 用基本类型 int 保存弹出值，再与辅助栈顶比较，比较的是数值而不是包装对象的引用身份。

解题步骤

  1. 初始化数据栈 data 和辅助栈 mins。
  2. 入栈时总是压入 data；若新值不大于当前最小值，或辅助栈为空，也压入 mins。
  3. 出栈时保存弹出值，只有它等于辅助栈顶时才同步弹出 mins。
  4. 栈顶查询读取 data，最小值查询读取 mins。

代码实现

class MinStack {
    private final Deque<Integer> data;
    private final Deque<Integer> mins;

    public MinStack() {
        data = new ArrayDeque<>();
        mins = new ArrayDeque<>();
    }

    public void push(int x) {
        data.push(x);

        // 相等的最小值也要保存，弹出时才能逐个对应。
        if (mins.isEmpty() || x <= mins.peek()) {
            mins.push(x);
        }
    }

    public void pop() {
        // 比较刚弹出的值；用 int 按数值比较，避免包装对象引用比较。
        int val = data.pop();

        if (val == mins.peek()) {
            mins.pop();
        }
    }

    public int top() {
        return data.peek();
    }

    public int min() {
        return mins.peek();
    }
}

type MinStack struct {
    data []int
    mins []int
}

func Constructor() MinStack {
    return MinStack{
        data: make([]int, 0),
        mins: make([]int, 0),
    }
}

func (s *MinStack) Push(x int) {
    s.data = append(s.data, x)

    // 相等的最小值也要保存，弹出时才能逐个对应。
    if len(s.mins) == 0 || x <= s.mins[len(s.mins)-1] {
        s.mins = append(s.mins, x)
    }
}

func (s *MinStack) Pop() {
    n := len(s.data)
    val := s.data[n-1]
    s.data = s.data[:n-1]

    // 只有弹出了当前最小值，辅助栈才同步弹出。
    if val == s.mins[len(s.mins)-1] {
        s.mins = s.mins[:len(s.mins)-1]
    }
}

func (s *MinStack) Top() int {
    return s.data[len(s.data)-1]
}

func (s *MinStack) Min() int {
    return s.mins[len(s.mins)-1]
}

复杂度分析

  • 时间复杂度：push 为摊还 $O(1)$，发生扩容的单次 push 为 $O(n)$；pop、top、min 为 $O(1)$。
  • 空间复杂度：$O(n)$，n 按执行过程中的最大栈规模计；底层数组弹出元素后不一定立即缩容。

关键点总结

[!green]

  • 相等也入栈，保证重复最小值有对应份数。
  • 比较的是刚弹出的值，而不是弹出后的新栈顶。
  • Java 用 int 接住弹出值，比较数值而不是 Integer 引用。

易错点总结

[!yellow]

  • 只保存严格更小值：会遗漏重复最小值的出现次数，弹出一份后可能过早丢失仍存在的最小值。
  • 每次出栈都弹出辅助栈：弹出的数据若不是最小值，辅助记录就不应改变。
  • 比较弹出后的新栈顶：需要判断的是刚离开的元素，而不是现在仍留在栈中的元素。
  • 查询最小值时执行弹出：查询不能破坏历史记录，必须读取栈顶。
  • 只保存一个最小值变量：最小元素离开后无法直接恢复之前的状态。

相似题目

题目 难度 关联与区别
716. 最大栈 困难 同样在栈操作中维护极值，原题还支持删除最大值，需要更复杂的定位与连接。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/42894963
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！