155. 最小栈
题目描述
设计一个栈类 MinStack。它支持常规的入栈、出栈和查看栈顶，还要能在常数时间内给出栈中的最小值。
需要实现的方法：
- MinStack()：创建一个空栈。
- void push(int val)：把 val 放到栈顶。
- void pop()：移除栈顶元素。
- int top()：返回栈顶元素。
- int getMin()：返回栈中当前的最小元素。
每个操作都应在 O(1) 时间内完成。
示例 1
输入：操作 = ["MinStack","push","push","push","getMin","pop","top","getMin"] 参数 = [[],[-2],[0],[-3],[],[],[],[]] 输出：[null,null,null,null,-3,null,0,-2]
解释：依次压入 -2、0、-3 后最小值是 -3；弹出 -3 后栈顶为 0，最小值变回 -2。
数据范围
-2^31 <= val <= 2^31 - 1- 调用
pop、top、getMin时栈一定非空。 push、pop、top、getMin合计最多调用3 * 10^4次。
解题思路：辅助最小值栈
主栈同步维护最小值栈。
为什么正确
辅助栈顶是当前最小值。
复杂度分析
每个操作的时间为 O(1)，额外空间 O(n)。
易错点
注意边界条件并在回溯或弹出后恢复状态。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class MinStack:
def __init__(self):self.s=[];self.m=[]
def push(self,x):self.s.append(x);self.m.append(x if not self.m else min(x,self.m[-1]))
def pop(self):self.s.pop();self.m.pop()
def top(self):return self.s[-1]
def getMin(self):return self.m[-1]class MinStack {
private final List<Integer> s = new ArrayList<>(), m = new ArrayList<>();
public MinStack() {}
public void push(int value) {
s.add(value);
m.add(m.isEmpty() ? value : Math.min(value, m.get(m.size() - 1)));
}
public void pop() {
s.remove(s.size() - 1);
m.remove(m.size() - 1);
}
public int top() {
return s.get(s.size() - 1);
}
public int getMin() {
return m.get(m.size() - 1);
}
}class MinStack {
vector<int> s, m;
public:
MinStack() {}
void push(int value) {
s.push_back(value);
m.push_back(m.empty() ? value : min(value, m.back()));
}
void pop() {
s.pop_back();
m.pop_back();
}
int top() {
return s.back();
}
int getMin() {
return m.back();
}
};type MinStack struct {
s, m []int
}
func Constructor() MinStack {
return MinStack{}
}
func (this *MinStack) Push(value int) {
this.s = append(this.s, value)
if len(this.m) == 0 {
this.m = append(this.m, value)
} else {
this.m = append(this.m, min(value, this.m[len(this.m)-1]))
}
}
func (this *MinStack) Pop() {
this.s = this.s[:len(this.s)-1]
this.m = this.m[:len(this.m)-1]
}
func (this *MinStack) Top() int {
return this.s[len(this.s)-1]
}
func (this *MinStack) GetMin() int {
return this.m[len(this.m)-1]
}var MinStack = function() {
this.s = [];
this.m = [];
};
MinStack.prototype.push = function(value) {
this.s.push(value);
this.m.push(this.m.length === 0 ? value : Math.min(value, this.m[this.m.length - 1]));
};
MinStack.prototype.pop = function() {
this.s.pop();
this.m.pop();
};
MinStack.prototype.top = function() {
return this.s[this.s.length - 1];
};
MinStack.prototype.getMin = function() {
return this.m[this.m.length - 1];
};class MinStack {
private s: number[] = [];
private m: number[] = [];
constructor() {}
push(value: number): void {
this.s.push(value);
this.m.push(this.m.length === 0 ? value : Math.min(value, this.m[this.m.length - 1]));
}
pop(): void {
this.s.pop();
this.m.pop();
}
top(): number {
return this.s[this.s.length - 1];
}
getMin(): number {
return this.m[this.m.length - 1];
}
}其他解法
两种方法每个操作都是 O(1)；辅助栈直观且不怕溢出，差值栈把最小值信息编码进差值里，省去第二个栈。
解法 2：差值栈 时间 O(1)，空间 O(n)
只用一个栈和一个变量 mn 保存当前最小值。入栈时压入 x - mn，若差值为负说明 x 成为新最小值，令 mn = x。出栈时若栈顶差值为负，说明弹出的是当前最小值，用 mn - diff 恢复上一个最小值。取栈顶时，差值为负返回 mn，否则返回 mn + diff。
省掉辅助栈，只多一个变量。差值可能超出 32 位整数范围，C++/Java 需要用 64 位整数存储，代码也更难读。
class MinStack:
def __init__(self):
self.s = []
self.mn = 0
def push(self, x):
if not self.s:
self.s.append(0)
self.mn = x
else:
d = x - self.mn
self.s.append(d)
if d < 0:
self.mn = x
def pop(self):
d = self.s.pop()
if d < 0:
self.mn -= d
def top(self):
d = self.s[-1]
return self.mn if d < 0 else self.mn + d
def getMin(self):
return self.mnclass MinStack {
private final Deque<Long> s = new ArrayDeque<>();
private long mn = 0;
public MinStack() {}
public void push(int value) {
if (s.isEmpty()) {
s.push(0L);
mn = value;
} else {
long d = value - mn;
s.push(d);
if (d < 0) mn = value;
}
}
public void pop() {
long d = s.pop();
if (d < 0) mn -= d;
}
public int top() {
long d = s.peek();
return (int) (d < 0 ? mn : mn + d);
}
public int getMin() {
return (int) mn;
}
}class MinStack {
vector<long long> s;
long long mn = 0;
public:
MinStack() {}
void push(int value) {
if (s.empty()) {
s.push_back(0);
mn = value;
} else {
long long d = value - mn;
s.push_back(d);
if (d < 0) mn = value;
}
}
void pop() {
long long d = s.back();
s.pop_back();
if (d < 0) mn -= d;
}
int top() {
long long d = s.back();
return (int)(d < 0 ? mn : mn + d);
}
int getMin() {
return (int)mn;
}
};type MinStack struct {
s []int
mn int
}
func Constructor() MinStack {
return MinStack{}
}
func (this *MinStack) Push(value int) {
if len(this.s) == 0 {
this.s = append(this.s, 0)
this.mn = value
} else {
d := value - this.mn
this.s = append(this.s, d)
if d < 0 {
this.mn = value
}
}
}
func (this *MinStack) Pop() {
d := this.s[len(this.s)-1]
this.s = this.s[:len(this.s)-1]
if d < 0 {
this.mn -= d
}
}
func (this *MinStack) Top() int {
d := this.s[len(this.s)-1]
if d < 0 {
return this.mn
}
return this.mn + d
}
func (this *MinStack) GetMin() int {
return this.mn
}var MinStack = function() {
this.s = [];
this.mn = 0;
};
MinStack.prototype.push = function(value) {
if (this.s.length === 0) {
this.s.push(0);
this.mn = value;
} else {
const d = value - this.mn;
this.s.push(d);
if (d < 0) this.mn = value;
}
};
MinStack.prototype.pop = function() {
const d = this.s.pop();
if (d < 0) this.mn -= d;
};
MinStack.prototype.top = function() {
const d = this.s[this.s.length - 1];
return d < 0 ? this.mn : this.mn + d;
};
MinStack.prototype.getMin = function() {
return this.mn;
};class MinStack {
private s: number[] = [];
private mn = 0;
constructor() {}
push(value: number): void {
if (this.s.length === 0) {
this.s.push(0);
this.mn = value;
} else {
const d = value - this.mn;
this.s.push(d);
if (d < 0) this.mn = value;
}
}
pop(): void {
const d = this.s.pop()!;
if (d < 0) this.mn -= d;
}
top(): number {
const d = this.s[this.s.length - 1];
return d < 0 ? this.mn : this.mn + d;
}
getMin(): number {
return this.mn;
}
}