LeetCode 155. 最小栈

155. 最小栈

解题思路

• push() 方法： 每当 push() 新值进来时，如果 新值 <= min_stack 的栈顶值，则把新值也存入 min_stack，使得 min_stack 的栈顶始终是整个栈 stack 中的最小值。
• pop() 方法： 每当 pop() 出栈时，如果 pop() 出来的值等于 min_stack 的栈顶值，则说明最小值被弹出了，此时也要把 min_stack 的栈顶元素弹出，这样 min_stack 的栈顶就会更新为新的最小值。
• top() 方法： 直接返回 stack 的栈顶元素即可。
• getMin() 方法： 直接返回 min_stack 的栈顶元素即可。

参考代码

class MinStack {
    private Stack<Integer> stack;
    // 维护一个辅助栈来存储当前最小的元素
    private Stack<Integer> min_stack;

    public MinStack() {
        stack = new Stack<>();
        min_stack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if(min_stack.isEmpty() || val <= min_stack.peek()) {
            min_stack.push(val);
        }
    }
    
    public void pop() {
        Integer top = stack.pop();
        // 如果弹出的元素是当前最小的元素，则辅助栈也要弹出
        if(top.equals(min_stack.peek())) {
            min_stack.pop();
        }

    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return min_stack.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();
 */