题目链接

栈的最小值

题目描述

注意点

• 执行push、pop和min操作的时间复杂度必须为O(1)

解答思路

• 使用两个栈，一个栈deque存储栈中对应的元素值，另一个栈minDeque存储当前栈中所有元素的最小值，当执行push(int x)操作，deque直接将x添加到栈中，minDeque将Math.min(minDeque.peek(), x)加入到栈中；当执行pop()操作，将deque和minDeque的栈顶元素都弹出即可

代码

class MinStack {
    Deque<Integer> deque;
    Deque<Integer> minDeque;

    /** initialize your data structure here. */
    public MinStack() {
        deque = new ArrayDeque<>();
        minDeque = new ArrayDeque<>();
        minDeque.push(Integer.MAX_VALUE);
    }
    
    public void push(int x) {
        deque.push(x);
        minDeque.push(Math.min(minDeque.peek(), x));
    }
    
    public void pop() {
        deque.pop();
        minDeque.pop();
    }
    
    public int top() {
        return deque.peek();
    }
    
    public int getMin() {
        return minDeque.peek();
    }
}

关键点

• 使用另一个栈存储当前栈中所有元素的最小值