Q：
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.
A：
如果是最小值轴术，那么push進來兩次，主要目的是在pop掉最小值的時候股毫，能夠還剩一個作為“存根”進行比對膳音，這是很巧妙地思路，“存”+比對后铃诬，再把第二個pop掉祭陷。
測試用例： 6，-2趣席，7兵志，4，-6宣肚。
陸續(xù)push進去之后想罕，stack里從上至下是：-6，-6霉涨，4按价，7，-2笙瑟，-2楼镐，6，6往枷。
class MinStack {
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; //單獨記錄下最小值是什么
}
stack.push(x); //（看上面的解釋）
}
public void pop() {
int top = stack.pop(); //是賦值語句框产，也完成了pop操作
if (top == min){
min = stack.pop(); //之前每次出現(xiàn)min就push進兩次凄杯，這里pop第二次
}
} //（看下面的代碼）
public int top() {
return stack.peek(); //import java.util.Stack
}
public int getMin() {
return min;
}
}
下面這個實現(xiàn) pop()的版本，含義完全一樣秉宿，雖然不夠簡潔戒突，但是更易懂！
(備注里寫了如何改動成上面精簡版本的步驟和邏輯過程)
public void pop() { if (stack.peek() == min) { //2.要pop()肯定是針對stack.peek()描睦，那直接stack.peek() = stack.pop()膊存，然后判斷是不是等于min
stack.pop();
min = stack.peek(); //4. 當(dāng)初存兩個目的就是為了這里酌摇，可以retrieve min value
stack.pop(); //5.已經(jīng)知道m(xù)in是啥了膝舅，可以把old min里的第二個“存根”也pop掉了
}
else { stack.pop();//1. 上面?zhèn)zpop()，這里又一個pop()窑多，說明無論如何都得pop()一次
} }
