| comments | difficulty | edit_url | tags | ||
|---|---|---|---|---|---|
true |
中等 |
|
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
示例 1:
输入： ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] 输出： [null,null,null,null,-3,null,0,-2] 解释： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
提示：
-231 <= val <= 231 - 1pop、top和getMin操作总是在 非空栈 上调用push,pop,top, andgetMin最多被调用3 * 104次
我们用两个栈来实现，其中 stk1 用来存储数据，stk2 用来存储当前栈中的最小值。初始时，stk2 中存储一个极大值。
- 当我们向栈中压入一个元素
$x$ 时，我们将$x$ 压入stk1，并将min(x, stk2[-1])压入stk2。 - 当我们从栈中弹出一个元素时，我们将
stk1和stk2的栈顶元素都弹出。 - 当我们要获取当前栈中的栈顶元素时，我们只需要返回
stk1的栈顶元素即可。 - 当我们要获取当前栈中的最小值时，我们只需要返回
stk2的栈顶元素即可。
每个操作的时间复杂度为
class MinStack:
def __init__(self):
self.stk1 = []
self.stk2 = [inf]
def push(self, val: int) -> None:
self.stk1.append(val)
self.stk2.append(min(val, self.stk2[-1]))
def pop(self) -> None:
self.stk1.pop()
self.stk2.pop()
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(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()class MinStack {
private Deque<Integer> stk1 = new ArrayDeque<>();
private Deque<Integer> stk2 = new ArrayDeque<>();
public MinStack() {
stk2.push(Integer.MAX_VALUE);
}
public void push(int val) {
stk1.push(val);
stk2.push(Math.min(val, 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(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/class MinStack {
public:
MinStack() {
stk2.push(INT_MAX);
}
void push(int val) {
stk1.push(val);
stk2.push(min(val, 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(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/type MinStack struct {
stk1 []int
stk2 []int
}
func Constructor() MinStack {
return MinStack{[]int{}, []int{math.MaxInt32}}
}
func (this *MinStack) Push(val int) {
this.stk1 = append(this.stk1, val)
this.stk2 = append(this.stk2, min(val, 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(val);
* obj.Pop();
* param_3 := obj.Top();
* param_4 := obj.GetMin();
*/class MinStack {
stk1: number[];
stk2: number[];
constructor() {
this.stk1 = [];
this.stk2 = [Infinity];
}
push(val: number): void {
this.stk1.push(val);
this.stk2.push(Math.min(val, this.stk2[this.stk2.length - 1]));
}
pop(): void {
this.stk1.pop();
this.stk2.pop();
}
top(): number {
return this.stk1[this.stk1.length - 1];
}
getMin(): number {
return this.stk2[this.stk2.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()
*/use std::collections::VecDeque;
struct MinStack {
stk1: VecDeque<i32>,
stk2: VecDeque<i32>,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl MinStack {
fn new() -> Self {
Self {
stk1: VecDeque::new(),
stk2: VecDeque::new(),
}
}
fn push(&mut self, x: i32) {
self.stk1.push_back(x);
if self.stk2.is_empty() || *self.stk2.back().unwrap() >= x {
self.stk2.push_back(x);
}
}
fn pop(&mut self) {
let val = self.stk1.pop_back().unwrap();
if *self.stk2.back().unwrap() == val {
self.stk2.pop_back();
}
}
fn top(&self) -> i32 {
*self.stk1.back().unwrap()
}
fn get_min(&self) -> i32 {
*self.stk2.back().unwrap()
}
}var MinStack = function () {
this.stk1 = [];
this.stk2 = [Infinity];
};
/**
* @param {number} val
* @return {void}
*/
MinStack.prototype.push = function (val) {
this.stk1.push(val);
this.stk2.push(Math.min(this.stk2[this.stk2.length - 1], val));
};
/**
* @return {void}
*/
MinStack.prototype.pop = function () {
this.stk1.pop();
this.stk2.pop();
};
/**
* @return {number}
*/
MinStack.prototype.top = function () {
return this.stk1[this.stk1.length - 1];
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function () {
return this.stk2[this.stk2.length - 1];
};
/**
* Your MinStack object will be instantiated and called as such:
* var obj = new MinStack()
* obj.push(val)
* obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.getMin()
*/public class MinStack {
private Stack<int> stk1 = new Stack<int>();
private Stack<int> stk2 = new Stack<int>();
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();
*/