栈----2.最小栈

155. 最小栈 - 力扣（LeetCode）

/**

        相较于传统的栈额外需要常数级时间复杂度获取栈中最小值

        双栈法:

            主栈,普通栈的功能,push、pop、top均在主栈进行

            辅助栈,记录当前状态主栈的最小值,即每当主栈状态发生改变时,辅助栈也要做相应更改

        辅助栈:

            push操作: 判断push后主栈的最小值,即辅助栈栈顶元素与待添加元素相比,将较小的值加入辅助栈中

            pop操作: 辅助栈也做相应pop操作,即减少一个状态

*/

class MinStack {/**相较于传统的栈额外需要常数级时间复杂度获取栈中最小值双栈法:主栈,普通栈的功能,push、pop、top均在主栈进行辅助栈,记录当前状态主栈的最小值,即每当主栈状态发生改变时,辅助栈也要做相应更改辅助栈:push操作: 判断push后主栈的最小值,即辅助栈栈顶元素与待添加元素相比,将较小的值加入辅助栈中pop操作: 辅助栈也做相应pop操作,即减少一个状态*///主栈private Deque<Integer> stack;//辅助栈private Deque<Integer> minStack;public MinStack() {stack = new ArrayDeque<>();minStack = new ArrayDeque<>();}//主栈直接添加,辅助栈保存当前状态主栈最小值public void push(int val) {//主栈直接添加元素stack.push(val);//辅助栈添加当前主栈状态的最小值if(minStack.isEmpty() || val <= minStack.peek()) {minStack.push(val);} else {minStack.push(minStack.peek());}}//删除主栈元素的同时,弹出主栈顶部元素public void pop() {stack.pop();minStack.pop();}public int top() {return stack.peek();}public int getMin() {return minStack.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();*/