155. Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) – Push element x onto stack.
- pop() – Removes the element on top of the stack.
- top() – Get the top element.
- getMin() – Retrieve the minimum element in the stack.
Example
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.
题意：这个题也是 stack 的经典题之一。题目要求设计一个 stack, 要求栈的 push，pop，top，getMin 都需要是常数复杂度的。 解法就是需要同时维护两个栈。 有一个栈放当前的最小元素。 为了简便，每 push 一个数，我们就将其和栈顶元素对比，压入较小的一个. 这样就可以记录所有状态下的最小值。
代码
class MinStack {
Stack<Integer> stack;
Stack<Integer> backup;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack<>();
backup = new Stack<>();
}
public void push(int x) {
stack.push(x);
if(backup.isEmpty()) {
backup.push(x);
} else {
backup.push(Math.min(backup.peek(), x));
}
}
public void pop() {
stack.pop();
backup.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return backup.peek();
}
}