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.
題意：自己實(shí)現(xiàn)一個(gè)棧
java代碼：
Stack<Integer> stack = new Stack<>(); //declaration one stack here
int min = Integer.MAX_VALUE; //先聲明min, no worry about stack.empty
public void push(int x) {
if (x <= min) {
stack.push(min);
min = x; //單獨(dú)記錄下最小值是什么
}
stack.push(x); //（看上面的解釋）
}
public void pop() {
int top = stack.pop(); //是賦值語(yǔ)句领猾，也完成了pop操作
if (top == min){
min = stack.pop(); //之前每次出現(xiàn)min就push進(jìn)兩次苹祟，這里pop第二次
}
}
public int top() {
return stack.peek(); //import java.util.Stack
}
public int getMin() {
return min;
}
