Implement a stack with min() function, which will return the smallest number in the stack.
It should support push, pop and min operation all in O(1) cost.
min operation will never be called if there is no number in the stack.
push(1)
pop() // return 1
push(2)
push(3)
min() // return 2
push(1)
min() // return 1
分析：
用另一个stack来保存当前最小的值。
1 public class MinStack { 2 3 Stack<Integer> elements = new Stack<Integer>(); 4 Stack<Integer> minStack = new Stack<Integer>(); 5 6 public MinStack() { 7 // do initialize if necessary 8 } 9 10 public void push(int x) { 11 elements.push(x); 12 if (minStack.isEmpty() || x <= minStack.peek()) { 13 minStack.push(x); 14 } 15 } 16 17 public int pop() { 18 if (elements.isEmpty()) { 19 return -1; 20 } 21 // 这个地方太蛋疼了，居然要用equals... 22 if (elements.peek().equals(minStack.peek())) { 23 minStack.pop(); 24 } 25 return elements.pop(); 26 } 27 28 public int min() { 29 return minStack.peek(); 30 } 31 }
原文：http://www.cnblogs.com/beiyeqingteng/p/5655137.html