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.
Example
push(1) pop() // return 1 push(2) push(3) min() // return 2 push(1) min() // return 1
1 public class MinStack { 2 private Stack<Integer> minStack; 3 private Stack<Integer> stack; 4 public MinStack() { 5 // do initialize if necessary 6 minStack = new Stack<Integer>(); 7 stack = new Stack<Integer>(); 8 } 9 10 public void push(int number) { 11 // write your code here 12 stack.push(number); 13 if (minStack.isEmpty()) { 14 minStack.push(number); 15 } else { 16 if(number <= minStack.peek()) { 17 minStack.push(number); 18 } 19 } 20 } 21 22 public int pop() { 23 // write your code here 24 //here you use equals which stand for two peeked values 25 //need to be exactly same. 26 //If they are both null, it also works 27 if (stack.peek().equals(minStack.peek())) { 28 minStack.pop(); 29 } 30 return stack.pop(); 31 } 32 33 public int min() { 34 // write your code here 35 return minStack.peek(); 36 } 37 }
In this problem, we want to get the current smallest value and implemnt a stack. The main issue is to get current smallest value. So we should use another stack to remember the current smallest values and delete them when we pop that value out.
Trcks: Use stack.peek().equals(minStack.peek()) instead of stack.peek() == minStack.peek() becuase peek() method could return null value and if they are both null it is also okay.
原文：http://www.cnblogs.com/ly91417/p/5808567.html