add min stack

fishercoder1534 · fishercoder1534 · commit c920110b9e1a · 2016-10-18T22:30:29.000-07:00
diff --git a/EASY/src/easy/MinStack.java b/EASY/src/easy/MinStack.java
@@ -0,0 +1,44 @@
+package easy;
+
+import java.util.*;
+
+public class MinStack {
+    
+    private Stack<Integer> stack;
+    private int min;
+
+    /** initialize your data structure here. */
+    public MinStack() {
+        stack = new Stack();
+        min = Integer.MAX_VALUE;
+    }
+    
+    public void push(int x) {
+        /**All the trick happens here, we push the second minimum number onto the stack before we push the newer one,
+         * this way, when popping, we could always get the next minimum one in constant time.*/
+        if(x <= min){
+            stack.push(min);
+            min = x;
+        }
+        stack.push(x);
+    }
+    
+    public void pop() {
+        if(min == stack.peek()){
+            stack.pop();
+            min = stack.pop();
+        } else {
+            stack.pop();
+        }
+        if(stack.isEmpty()) min = Integer.MAX_VALUE;
+    }
+    
+    public int top() {
+        return stack.peek();
+    }
+    
+    public int getMin() {
+        return min;
+    }
+
+}
diff --git a/README.md b/README.md
@@ -27,6 +27,7 @@
 |173|[Binary Search Tree Iterator](https://leetcode.com/problems/binary-search-tree-iterator/)|[Queue](../../blob/master/MEDIUM/src/medium/BSTIterator_using_q.java) [Stack](../../blob/master/MEDIUM/src/medium/BSTIterator_using_stack.java)| O(1) |O(h) | Medium|
 |172|[Factorial Trailing Zeroes](https://leetcode.com/problems/factorial-trailing-zeroes/)|[Solution](../../blob/master/EASY/src/easy/FactorialTrailingZeroes.java)| O(logn)|O(1)| Easy
 |162|[Find Peak Element](https://leetcode.com/problems/find-peak-element/)|[Solution](../../blob/master/MEDIUM/src/medium/FindPeakElement.java) | O(1) |O(logn)/O(n) | Binary Search|
+|155|[Min Stack](https://leetcode.com/problems/min-stack/)|[Solution](../../blob/master/EASY/src/easy/MinStack.java)| O(1)|O(n) | Easy| Stack
 |140|[Word Break II](https://leetcode.com/problems/word-break-ii/)|[Solution](../../blob/master/HARD/src/hard/WordBreakII.java)| ? |O(n^2) | Hard| Backtracking/DFS
 |139|[Word Break](https://leetcode.com/problems/word-break/)|[Solution](../../blob/master/MEDIUM/src/medium/WordBreak.java)| O(n^2)|O(n) | Medium| DP
 |133|[Clone Graph](https://leetcode.com/problems/clone-graph/)|[Solution](../../blob/master/MEDIUM/src/medium/CloneGraph.java)| O(n)|O(n) | Medium| HashMap, BFS 
