30. 包含 min 函数的栈

---

comments: true
difficulty: 简单
edit_url: https://github.com/doocs/leetcode/edit/main/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9830.%20%E5%8C%85%E5%90%ABmin%E5%87%BD%E6%95%B0%E7%9A%84%E6%A0%88/README.md

面试题 30. 包含 min 函数的栈

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

 

示例:

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

 

提示：

1. 各函数的调用总次数不超过 20000 次

 

注意：本题与主站 155 题相同：https://leetcode.cn/problems/min-stack/

解法

方法一：双栈

我们用两个栈来实现，其中stk1 用来存储数据，stk2 用来存储当前栈中的最小值。初始时，stk2 中存储一个极大值。

• 当我们向栈中压入一个元素 x 时，我们将 x 压入 stk1，并将 min(x, stk2[-1]) 压入 stk2。
• 当我们从栈中弹出一个元素时，我们将 stk1 和 stk2 的栈顶元素都弹出。
• 当我们要获取当前栈中的栈顶元素时，我们只需要返回 stk1 的栈顶元素即可。
• 当我们要获取当前栈中的最小值时，我们只需要返回 stk2 的栈顶元素即可。

时间复杂度：对于每个操作，时间复杂度均为 $O(1)$，空间复杂度 $O(n)$。

Python3

class MinStack:def __init__(self):self.stk1 = []self.stk2 = [inf]def push(self, x: int) -> None:#难点：stk2每个位置的元素，对应 stk1对应位置元素 至 栈地元素的 最小值self.stk1.append(x)self.stk2.append(min(x, self.stk2[-1]))def pop(self) -> None:self.stk1.pop() # 1 2 3 0 0 5(顶)self.stk2.pop() # 1 1 1 0 0 0(顶)def top(self) -> int:return self.stk1[-1]def getMin(self) -> int:return self.stk2[-1]# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

Java

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();}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(x);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/

C++

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;
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(x);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/

Go

type MinStack struct {stk1 []intstk2 []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]
}/*** Your MinStack object will be instantiated and called as such:* obj := Constructor();* obj.Push(x);* obj.Pop();* param_3 := obj.Top();* param_4 := obj.GetMin();*/

TypeScript

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];}
}/*** Your MinStack object will be instantiated and called as such:* var obj = new MinStack()* obj.push(x)* obj.pop()* var param_3 = obj.top()* var param_4 = obj.getMin()*/

Rust

use std::collections::VecDeque;
struct MinStack {stack: VecDeque<i32>,min_stack: VecDeque<i32>,
}/*** `&self` means the method takes an immutable reference.* If you need a mutable reference, change it to `&mut self` instead.*/
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()}
}

JavaScript

/*** initialize your data structure here.*/
var MinStack = function () {this.stack = [];this.minStack = [];
};/*** @param {number} x* @return {void}*/
MinStack.prototype.push = function (x) {this.stack.unshift(x);if (!this.minStack.length || this.minStack[0] >= x) {this.minStack.unshift(x);}
};/*** @return {void}*/
MinStack.prototype.pop = function () {if (this.stack.shift() === this.minStack[0]) {this.minStack.shift();}
};/*** @return {number}*/
MinStack.prototype.top = function () {return this.stack[0];
};/*** @return {number}*/
MinStack.prototype.min = function () {return this.minStack[0];
};/*** Your MinStack object will be instantiated and called as such:* var obj = new MinStack()* obj.push(x)* obj.pop()* var param_3 = obj.top()* var param_4 = obj.min()*/

C#

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();}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.Push(x);* obj.Pop();* int param_3 = obj.Top();* int param_4 = obj.GetMin();*/

Swift

class MinStack {private var stack: [Int]private var minStack: [Int]init() {stack = []minStack = [Int.max]}func push(_ x: Int) {stack.append(x)minStack.append(min(x, minStack.last!))}func pop() {stack.removeLast()minStack.removeLast()}func top() -> Int {return stack.last!}func getMin() -> Int {return minStack.last!}
}/*** Your MinStack object will be instantiated and called as such:* let obj = MinStack();* obj.push(x);* obj.pop();* let param_3 = obj.top();* let param_4 = obj.getMin();*/