企业官网建设流程全解析

• 示例工程
• 教程

本文以 doocs/leetcode 仓库中《程序员面试金典（第 6 版）》题解目录下的 面试题 03.02. 栈的最小值 为核心，系统讲解如何设计一个支持push、pop、top、getMin四种操作且全部达到 O(1) 时间复杂度的最小值栈，并逐语言剖析仓库中 Python3、Java、C++、Go、TypeScript、Rust、C#、Swift 八种官方题解的实现细节与变体思路。读完本文，你将掌握"双栈同步维护前缀最小值"这一经典设计模式，能够独立复现并应对同类"辅助栈"面试题。

题目背景：在 O(1) 时间内回答"栈里最小是谁"

本题出自 LeetCode《程序员面试金典》面试题 03.02（题目编号 Min Stack，仓库路径 lcci/03.02.Min Stack/README.md，英文版见 README_EN.md）。题目要求设计一个栈，在常规栈支持的push与pop之外，额外提供min（即getMin）函数返回栈元素中的最小值，并且push、pop和min操作的时间复杂度都必须为 O(1)。

题目给出的操作示例：

MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.

核心难点在于：如果getMin每次都扫描全部元素求最小值，该操作就是线性的（O(n)），无法与 O(1) 的push/pop匹配。必须在入栈/出栈的过程中把最小值信息"存起来"。

解法一：双栈——用辅助栈同步记录每个前缀的最小值

核心思想

仓库题解采用**双栈（Double Stack）**方案，思路可以归纳为三点：

1. 前缀最小值在压入时即可确定：每当一个新元素入栈，栈内"当前最小值"要么是上一个最小值，要么是新元素本身，二者取小即可，无需扫描全栈；
2. 弹出时自动回退：元素弹出后，栈回到了上一个前缀状态，最小值也随之回退到上一个前缀的最小值，天然满足栈的 LIFO 语义；
3. 辅助栈与数据栈严格同步：额外维护一条与数据栈同步弹出的"当前最小"栈，getMin只需读取辅助栈栈顶，即为 O(1)。

具体地，用stk1存储数据，用stk2存储当前栈中的最小值，初始时stk2中放入一个极大值（各语言的+∞表示见下文）。四种操作规则为：

该方案的时间复杂度：每个操作均为 O(1)；空间复杂度 O(n)（stk2与数据栈同规模）。

Python3

仓库 Solution.py 中利用 Python 列表天然支持append/pop/下标访问的特性实现，inf表示正无穷作为初始极大值：

class MinStack: def __init__(self): """ initialize your data structure here. """ self.s = [] self.mins = [inf] def push(self, val: int) -> None: self.s.append(val) self.mins.append(min(self.mins[-1], val)) def pop(self) -> None: self.s.pop() self.mins.pop() def top(self) -> int: return self.s[-1] def getMin(self) -> int: return self.mins[-1] # Your MinStack object will be instantiated and called as such: # obj = MinStack() # obj.push(val) # obj.pop() # param_3 = obj.top() # param_4 = obj.getMin()

要点：self.mins = [inf]保证首次push时min(inf, val)恒等于val，避免了"空栈取最小值"的特判。

Java

仓库 Solution.java 使用ArrayDeque作为栈实现，构造时向stk2压入Integer.MAX_VALUE：

class MinStack { private Deque<Integer> stk1 = new ArrayDeque<>(); private Deque<Integer> stk2 = new ArrayDeque<>(); /** initialize your data structure here. */ public MinStack() { stk2.push(Integer.MAX_VALUE); } public void push(int x) { stk1.push(x); stk2.push(Math.min(x, stk2.peek())); } public void pop() { stk1.pop(); stk2.pop(); } public int top() { return stk1.peek(); } public int getMin() { return stk2.peek(); } }

注意stk2的栈顶在push时是尚未压入新值前的上一个最小值，因此Math.min(x, stk2.peek())与上文min(x, stk2[-1])完全等价。

C++

仓库 Solution.cpp 使用标准库std::stack，用INT_MAX作为初始极大值：

class MinStack { public: /** initialize your data structure here. */ MinStack() { stk2.push(INT_MAX); } void push(int x) { stk1.push(x); stk2.push(min(x, stk2.top())); } void pop() { stk1.pop(); stk2.pop(); } int top() { return stk1.top(); } int getMin() { return stk2.top(); } private: stack<int> stk1; stack<int> stk2; };

Go

仓库 Solution.go 用切片模拟栈，Constructor返回结构体时把stk2初始化为[]int{math.MaxInt32}，出栈通过切片截断stk[:len(stk)-1]完成：

type MinStack struct { stk1 []int stk2 []int } /** initialize your data structure here. */ func Constructor() MinStack { return MinStack{[]int{}, []int{math.MaxInt32}} } func (this *MinStack) Push(x int) { this.stk1 = append(this.stk1, x) this.stk2 = append(this.stk2, min(x, this.stk2[len(this.stk2)-1])) } func (this *MinStack) Pop() { this.stk1 = this.stk1[:len(this.stk1)-1] this.stk2 = this.stk2[:len(this.stk2)-1] } func (this *MinStack) Top() int { return this.stk1[len(this.stk1)-1] } func (this *MinStack) GetMin() int { return this.stk2[len(this.stk2)-1] }

Go 代码中的min为 Go 1.21+ 内置函数；math.MaxInt32需要import "math"。

TypeScript

仓库 Solution.ts 直接使用数组，getMin在mins为空时返回Infinity，因此在push中通过Math.min(this.getMin(), x)亦可正确写入首个最小值：

class MinStack { stack: number[]; mins: number[]; constructor() { this.stack = []; this.mins = []; } push(x: number): void { this.stack.push(x); this.mins.push(Math.min(this.getMin(), x)); } pop(): void { this.stack.pop(); this.mins.pop(); } top(): number { return this.stack[this.stack.length - 1]; } getMin(): number { return this.mins.length == 0 ? Infinity : this.mins[this.mins.length - 1]; } }

C#

仓库 Solution.cs 使用System.Collections.Generic.Stack<int>，构造时将int.MaxValue压入stk2：

public class MinStack { private Stack<int> stk1 = new Stack<int>(); private Stack<int> stk2 = new Stack<int>(); /** initialize your data structure here. */ public MinStack() { stk2.Push(int.MaxValue); } public void Push(int x) { stk1.Push(x); stk2.Push(Math.Min(x, GetMin())); } public void Pop() { stk1.Pop(); stk2.Pop(); } public int Top() { return stk1.Peek(); } public int GetMin() { return stk2.Peek(); } }

C# 与 Java 同属"栈顶即上一个最小值"的写法：stk2.Push(Math.Min(x, GetMin()))中GetMin()取到的是压入前的旧栈顶。

Swift

仓库 Solution.swift 用数组实现，init中将stk2初始化为[Int.max]：

class MinStack { private var stk1: [Int] private var stk2: [Int] init() { stk1 = [] stk2 = [Int.max] } func push(_ x: Int) { stk1.append(x) stk2.append(min(x, stk2.last!)) } func pop() { stk1.removeLast() stk2.removeLast() } func top() -> Int { return stk1.last! } func getMin() -> Int { return stk2.last! } }

解法二（变体）：Rust 的最小值栈"按需入栈"优化

仓库 Solution.rs 没有照搬"每压必入"的双栈，而是采用仅在出现新的（或相等的）最小值时才入辅助栈的变体，从而在数据单调递增时显著节省辅助栈空间：

use std::collections::VecDeque; struct MinStack { stack: VecDeque<i32>, min_stack: VecDeque<i32>, } impl MinStack { /** initialize your data structure here. */ fn new() -> Self { Self { stack: VecDeque::new(), min_stack: VecDeque::new(), } } fn push(&mut self, x: i32) { self.stack.push_back(x); if self.min_stack.is_empty() || *self.min_stack.back().unwrap() >= x { self.min_stack.push_back(x); } } fn pop(&mut self) { let val = self.stack.pop_back().unwrap(); if *self.min_stack.back().unwrap() == val { self.min_stack.pop_back(); } } fn top(&self) -> i32 { *self.stack.back().unwrap() } fn get_min(&self) -> i32 { *self.min_stack.back().unwrap() } }

这段代码与"双栈同步"方案在push/pop上的差异值得注意：

• push：只有min_stack为空，或新元素x不大于当前辅助栈栈顶（即>=判断通过）时，才把x写入min_stack；否则说明x不是新最小值，无需记录；
• pop：先从stack弹出val，仅当val恰好等于min_stack栈顶时，才同步弹出辅助栈——因为只有最小值被弹走，当前最小值才会回退；
• 条件中的>=保留了相等元素的重复记录：例如连续压入两个-3，辅助栈会记录两次，避免弹出其中一个-3后最小值栈被错误清空。这是该变体正确性的关键细节。

两种方案各操作的时间复杂度均为 O(1)；空间复杂度上，双栈同步版固定为 O(n)，Rust 变体在最坏情况（严格递减序列）下同样为 O(n)，但在单调不减序列下辅助栈可退化为常数规模，属于"最坏相同、平均更省"的优化写法。

复杂度与正确性小结

• 时间复杂度：push、pop、top、getMin全部为 O(1)。top读数据栈栈顶、getMin读辅助栈栈顶，都是常数时间；push/pop只做一次压栈/弹栈与一次比较。
• 空间复杂度：双栈同步方案为 O(n)，其中 n 为栈中元素个数。
• 正确性依据：最小值具有"前缀单调性"——栈从底部到栈顶的任意前缀，其最小值在元素压入时即被固化在辅助栈的对应位置上；弹出元素等价于回退到上一前缀，辅助栈同步弹出后栈顶依然对应当前前缀的最小值。因此无论执行序列如何交织，getMin返回值始终与栈内实际最小值一致。

仓库中该题的全部实现均可对照查看：Python3（Solution.py）、Java（Solution.java）、C++（Solution.cpp）、Go（Solution.go）、TypeScript（Solution.ts）、Rust（Solution.rs）、C#（Solution.cs）、Swift（Solution.swift），多语言代码与本文完全一致。

延伸：同目录下的相关栈题目

本类"辅助栈"设计在《程序员面试金典》栈与队列章节中反复出现，可在仓库 lcci 目录下继续练习：

• 03.01. 三合一（Three in One）：单个数组实现三个栈；
• 03.03. 堆盘子（Stack of Plates）：多栈分层管理；
• 03.04. 化栈为队（Implement Queue using Stacks）：双栈模拟队列，与本题"双栈各司其职"的思维同源；
• 03.05. 栈排序（Sort of Stacks）：借助辅助栈完成排序，是"辅助栈"思路的又一典型应用。

掌握了"用辅助数据结构换取 O(1) 查询、与主结构同步维护"这一模式，应对上述题目时便能举一反三。

• 示例工程
• 教程