image.png

解题思路

每次如果当前值比最小值还要小,则将第二小的值入栈,这样即使最小值出栈后也有最小值信息
代码

  1. class MinStack {
  2. int min = Integer.MAX_VALUE;
  3. Stack<Integer> stack = new Stack<Integer>();
  4. public void push(int x) {
  5. // only push the old minimum value when the current
  6. // minimum value changes after pushing the new value x
  7. if(x <= min){
  8. stack.push(min);
  9. min=x;
  10. }
  11. stack.push(x);
  12. }
  13. public void pop() {
  14. // if pop operation could result in the changing of the current minimum value,
  15. // pop twice and change the current minimum value to the last minimum value.
  16. if(stack.pop() == min) min=stack.pop();
  17. }
  18. public int top() {
  19. return stack.peek();
  20. }
  21. public int getMin() {
  22. return min;
  23. }
  24. }