题目描述:
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.
中文理解:实现栈操作,能够在O(1)时间内取到最小的数。
解题思路:采用两个两个栈,同步操作,主栈来正常存储取数据,辅助栈跟着主栈的操作,一样操作,只不过压栈时主栈入数,辅助栈入最小的数。
代码(java):
class MinStack {
/** initialize your data structure here. */
Stack<Integer> mainStack=new Stack<Integer>();
Stack<Integer> stack=new Stack<Integer>();
public MinStack() {
}
public void push(int x) {
mainStack.push(x);
stack.push(stack.isEmpty() ? x : Math.min(x, stack.peek()));
}
public void pop() {
mainStack.pop();
stack.pop();
}
public int top() {
return mainStack.peek();
}
public int getMin() {
return stack.peek();
}
}