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.

這是一道關于棧的題目，整體來說比較簡單。我最開始想的時候想的太簡單，以為使用一個棧st, 再維護一個最小值變量就好了。突然發(fā)現(xiàn)pop()操作之后需要更新這個最小值，那就需要知道第二小的值，這個第二小的值怎么找呢？于是乎我想到了使用另外一個棧minst專門來存儲最小值。push()操作的時候每當x小于或等于（注意不是小于，之所以小于等于是為了元素重復的情況）minst的棧頂元素，minst也push x入棧。pop()操作時，如果pop出來的元素等于minst棧頂元素，那么minst棧也出棧。

這道題思路很簡單，到時語法卡了我一會兒，老是過不了，一段時間不練手生啊。我的語法問題又出在==跟equals()上面。我棧的定義是Stack<Integer>。Integer是一個object。那么判斷兩個棧棧頂元素相等就不能寫成 st.peek() == minst.peek()，這是地址相等，equals才是值相等。要改的話要么就改用equals，要么定義一個int elem = st.pop(); 再判斷if (elem == minst.peek()), 這里是一個int 變量跟Integer對象相比，而不是兩個Integer對象相比，==在這里就是表示值相等。

 1 class MinStack { 2     Stack<Integer> st; 3     Stack<Integer> minst; 4      5     public MinStack() { 6         this.st = new Stack<Integer>(); 7         this.minst = new Stack<Integer>(); 8     } 9     10     public void push(int x) {11         st.push(x);12         if (minst.empty() || minst.peek()>=x) {13             minst.push(x);14         }15     }16 17     public void pop() {18         if (st.isEmpty()) {19             return;20         }21         if (st.peek().equals(minst.peek())) {22             minst.pop();23         }24         st.pop();25     }26 27     public int top() {28         if (!st.isEmpty()) {29             return st.peek();30         }31         return Integer.MAX_VALUE;32     }33 34     public int getMin() {35         if (!minst.isEmpty()) {36             return minst.peek();37         }38         return Integer.MAX_VALUE;39     }40 }