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

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

题目描述

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

image-20241107205549934

题意分析

要设计一个栈，除了常规的 push / pop / top，还要能随时返回栈内的最小值，四个操作都要求 $O(1)$ 时间。

「$O(1)$ 拿最小值」这一条本身就排除了查询时现算的做法：最小值必须被预先维护成一份状态，而不是每次遍历栈求出来。

真正给出解法方向的约束是后进先出——pop 只会从栈顶删元素，永远不会从中间删。这意味着「当前最小值」的变化是可预测、可撤销的：栈顶被删掉后，最小值必然回到上一个历史时刻的取值。若题目允许删除任意位置的元素（比如 716 题的 popMax），这个性质立刻失效。

边界有两处：题目保证 pop、top、min 都在栈非空时调用，所以不必设计空栈的返回值；但元素可以重复、可以为负，这两点会直接决定比较符号怎么写。

解法：辅助最小栈

核心思路

暴力做法是只用一个栈，min() 时把元素全倒到临时容器里扫一遍求最小值再倒回来。功能正确，但单次 min() 就是 $O(n)$，连续查询退化成 $O(n^2)$。瓶颈很清楚：同一份最小值信息被反复重算。

关键观察是，栈的内容随时间只在栈顶增删，所以「栈内最小值」这个量也只随栈顶增删而变化：第 k 次 push 之后的最小值 = 第 k-1 次之后的最小值与新元素取小；而弹掉栈顶之后，最小值必然回到弹出前的上一个取值。也就是说，最小值的历史序列本身就是一个栈。

于是用第二个栈 mins 记录这些历史最小值。不变量：mins 的栈顶恒等于 data 中全部元素的最小值，且 mins 自栈底到栈顶单调不增。 每个 push / pop 只做常数次操作来维持这条不变量。

push 时只在 x <= mins.peek() 成立时才同步压入，这里必须取非严格的 <=。若写成 <，push(2)、push(2) 之后 mins 里只存了一个 2，一次 pop 就把它弹空，剩下那个 2 再没人代表。用 <= 意味着重复的最小值有几个就在 mins 里占几格，pop 时一格一格还回去，份数天然对齐。

pop 的条件与之对称：val == mins.peek()。只有被弹出的元素正好是当前最小值，它才在 mins 里占了一格，才需要同步弹出。

解题步骤

  • 两个栈一起初始化：data 存全部元素，mins 存最小值历史。之所以分开存而不是在 data 里压 (值, 当时最小值) 二元组，是为了让 mins 在没有产生新最小值时完全不增长。
  • push 先压 data，再判断是否压 mins：判断条件必须把 mins.isEmpty() 写在前面并利用短路，否则第一次 push 就会在空栈上取栈顶。
  • push 的比较用 x <= mins.peek()：等号为重复的最小值留出对应份数，理由见核心思路。
  • pop 先从 data 弹出并用变量接住返回值，再拿它与 mins.peek() 比较：必须接住这个值，不接住就只能看 data.peek()，而此时栈顶已经换成了下一个元素，比的对象根本不对。
  • top 与 min 只做 peek 不做 pop：min() 是查询而非消费，写成 mins.pop() 会把历史信息永久破坏。

以操作序列 push(-2), push(0), push(-3), min(), pop(), top(), min() 走一遍。

push(-2)：data = [-2]；mins 为空，直接压入，mins = [-2]。
push(0)：data = [-2, 0]；0 <= -2 不成立，mins 不动，仍为 [-2]。
push(-3)：data = [-2, 0, -3]；-3 <= -2 成立，mins = [-2, -3]。
min()：返回 mins 栈顶 -3，与 data 的真实最小值一致。
pop()：从 data 弹出 -3，data = [-2, 0]；弹出值等于 mins 栈顶 -3，同步弹出，mins = [-2]。
top()：返回 data 栈顶 0。
min()：返回 mins 栈顶 -2，正是 [-2, 0] 的最小值，不变量始终成立。

换成 push(2), push(2), pop(), min() 检验等号的必要性：若 push 用严格 <，第二次 push 不入 mins，mins = [2]；pop() 弹出的 2 等于 mins 栈顶，把唯一那格也弹了，mins 变空，紧接着的 min() 就在空栈上取值。

代码实现

// 辅助栈保存当前最小值，当压入元素小于等于最小值时同步入栈。
import java.util.ArrayDeque;
import java.util.Deque;

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 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]
}

复杂度分析

  • 时间复杂度：$O(1)$，凭的是四个操作内部都只有常数次栈顶读写和一次比较，没有任何循环。
  • 空间复杂度：$O(n)$，data 存下全部 n 个元素；mins 在元素严格递减入栈的最坏情况下也存 n 个，合计仍是线性。

关键点总结

  • $O(1)$ 查询极值的通用套路是「把答案维护成状态」，而不是「查询时再算」，代价是每次修改都要顺带更新这份状态。
  • 辅助栈成立的前提是只在栈顶增删，这让最小值的历史可以精确回退。若还要支持删除任意位置的最大值，单纯的辅助栈就不够了，需要双向链表维护栈顺序、再用有序映射定位最大值。
  • 相等时也入栈（<=）是这类计数型辅助结构的通用写法：让重复元素各占一格，删除时才能一一对应。
  • 存在等价的单栈写法——入栈时压入「当前值与当时最小值的差」，或直接压 (val, curMin) 二元组。面试官追问空间优化时可以提，但差值写法有溢出风险，白板上首选辅助栈。

易错点总结

  • 错误写法：push 的比较用严格 x < mins.peek()：push(2), push(2), pop(), min() → mins 被提前弹空，min() 在空栈上取值，抛异常或返回垃圾值。
  • 错误写法：push 时不先短路判 mins.isEmpty()：第一次 push(1) 就在空的 mins 上调 peek()，Java 得到 null 后自动拆箱抛 NullPointerException。
  • 错误写法：pop 时不接住 data 弹出的值，直接拿 data.peek() 去比：push(1), push(2), pop() → 弹出 2 后拿新栈顶 1 与 mins 栈顶 1 比较，条件成立，把仍在 data 里的最小值 1 从 mins 中错误弹出，之后 min() 会读空栈。
  • 错误写法：pop 时无条件同步弹 mins：push(1), push(5), pop(), min() → mins 只有一格 1 却被弹空，min() 崩溃。
  • 错误写法：min() 里写 return mins.pop()：push(3), min(), min() → 第一次返回 3 并把 mins 弹空，第二次直接读空栈。
  • 错误写法：把 data.pop() 的返回值声明成 Integer 再用 == 与 mins.peek() 比：200 超出常见的 Integer 缓存范围，两个栈中的包装对象可能不是同一引用。执行 push(200), push(200), pop(), pop(), push(300), min() 时，旧的 200 可能留在 mins 中，错误返回 200。像代码中那样接成 int，比较时按数值拆箱即可。
  • 错误写法：只用一个 min 变量而不用栈：push(5), push(1), pop(), min() → 变量仍是 1，返回已被弹出的元素，正确答案是 5。单变量无法回退，是本题的核心陷阱。
  • 错误写法：用 ArrayDeque 时一端 push 另一端 pollLast：ArrayDeque.push 等价于 addFirst，混用就变成了队列语义，push(1), push(2), top() 会返回 1 而不是 2。
  • 错误写法：Go 版 Pop 里先切 mins 再切 data，且用 s.data[len(s.data)-1] 取被弹值：切片长度已变，取到的是新栈顶，Push(1), Push(2), Pop(), Min() 同样会把 mins 里的 1 错误弹出。

相似题目

题目 难度 考察点
155. 最小栈 中等 完全同题，只是接口名叫 getMin，可直接套用本文代码
面试题 03.02. 栈的最小值 简单 同题的第三个版本，适合用来检验是否真记住了 <= 这个等号
716. 最大栈 困难 多了 popMax，要删中间元素，后进先出前提被打破，辅助栈失效，需双向链表加有序表
895. 最大频率栈 困难 维护的极值从「值最小」变成「频率最高且最靠上」，要按频率分层建多个栈
剑指 Offer 09. 用两个栈实现队列 简单 同样是双栈协作，但两栈是「输入 / 输出」分工，复杂度要靠摊还分析说明
剑指 Offer 31. 栈的压入、弹出序列 中等 不设计结构，而是用一个栈模拟并验证给定弹出序列是否合法