请设计一个栈,除了常规栈支持的pop与push函数以外,还支持min函数,该函数返回栈元素中的最小值。执行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.
利用辅助栈存放栈的最小元素。
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.s = []
self.mins = [float('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()
class MinStack {
private Deque<Integer> s;
private Deque<Integer> mins;
/** initialize your data structure here. */
public MinStack() {
s = new ArrayDeque<>();
mins = new ArrayDeque<>();
mins.push(Integer.MAX_VALUE);
}
public void push(int val) {
s.push(val);
mins.push(Math.min(mins.peek(), val));
}
public void pop() {
s.pop();
mins.pop();
}
public int top() {
return s.peek();
}
public int getMin() {
return mins.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 {
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()
*/
type MinStack struct {
stack []int
minStack []int
}
/** initialize your data structure here. */
func Constructor() MinStack {
return MinStack{
stack: make([]int, 0),
minStack: make([]int, 0),
}
}
func (this *MinStack) Push(x int) {
this.stack = append(this.stack, x)
if len(this.minStack) == 0 || x <= this.minStack[len(this.minStack)-1] {
this.minStack = append(this.minStack, x)
}
}
func (this *MinStack) Pop() {
v := this.stack[len(this.stack)-1]
this.stack = this.stack[:len(this.stack)-1]
if v == this.minStack[len(this.minStack)-1] {
this.minStack = this.minStack[:len(this.minStack)-1]
}
}
func (this *MinStack) Top() int {
return this.stack[len(this.stack)-1]
}
func (this *MinStack) GetMin() int {
return this.minStack[len(this.minStack)-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();
*/