《剑指offer第二版》面试题30：包含min函数的栈（java）

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素min的函数。在该栈中，min、push、pop的时间复杂度都是O(1)

解题思路:

1. 定义两个栈，stack用于存储正常的栈元素，一个辅助栈minStack，用于保存最小值。
2. 当数据data入栈的时候，比较data和minStack栈顶元素的大小，将两者的最小值入栈minStack。minStack的栈顶元素就是栈的最小值。
3. 获取最小值的时候，只需返回minStack的栈顶元素即可。

代码

static class StackWithMin {
     private Stack<Integer> stack = new Stack<>();
     private Stack<Integer> min = new Stack<>();

     public void push(int data){
         stack.push(data);
         if (min.isEmpty()) {
             min.push(data);
         } else {
             min.push(data < min.peek() ? data : min.peek());
         }
     }

     public int pop(){
         if (stack.isEmpty()) {
             throw new RuntimeException("empty stack!!");
         }
         min.pop();
         return stack.pop();
     }

     public int min(){
         if (stack.isEmpty()) {
             throw new RuntimeException("empty stack!!");
         }
         return min.peek();
     }
 }