【leetcode hot 100 155】最小栈

解法一：栈+辅助栈

用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。

• 当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；
• 当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出；
• 在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。

class MinStack {Deque<Integer> stack;Deque<Integer> stack_min;public MinStack() {stack = new LinkedList<Integer>();stack_min = new LinkedList<Integer>();stack_min.push(Integer.MAX_VALUE);  // 初始化先放入一个最大整数，方便之后push时判断}public void push(int val) {stack.push(val);stack_min.push(Math.min(val, stack_min.peek()));}public void pop() {stack.pop();stack_min.pop();}public int top() {return stack.peek();}public int getMin() {return stack_min.peek();}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(val);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/

注意：

• 初始化时，辅助栈stack_min先放入一个最大整数，方便之后push时判断：stack_min.push(Integer.MAX_VALUE);