[LeetCode Hot 100] LeetCode155. 最小栈

题目描述

思路一：使用辅助栈

• 定义一个[数据栈]来支持push、pop、top操作
• 定义一个[辅助栈]，其栈顶为当前的最小值，以支持常数时间复杂度的getMin操作

思路二：使用ArrayDeque

• 栈元素中除了保存当前值之外，额外保存当前最小值
• 使用静态内部类

方法一：对应思路一

class MinStack {
    private Deque<Integer> stack;
    // 用于记录栈中的最小值
    private Deque<Integer> minStack;

    public MinStack() {
        stack = new ArrayDeque<>();
        minStack = new ArrayDeque<>();
    }
    
    public void push(int val) {
        // 这里需要是<=号,即当为最小值是数据栈和辅助栈都需要push
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
        stack.push(val);
    }
    
    public void pop() {
        // 注意:stack.pop()和minStack.peek()都是Integer类型
        // 它们的比较不能用==，因为==用于包装类型的比较,比较的是它们的地址,需要用equals方法
        if (!minStack.isEmpty() && !stack.isEmpty() && stack.pop().equals(minStack.peek())) {
            minStack.pop();
        }
    }
    
    public int top() {
        if (!stack.isEmpty()) {
            return stack.peek();
        }
		// 如果报错,可以返回一个异常
        throw new RuntimeException("栈中元素为空，此操作非法");
    }
    
    public int getMin() {
        if (!minStack.isEmpty()) {
            return minStack.peek();
        }
        throw new RuntimeException("栈中元素为空，此操作非法");
    }
}

/**
 * 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();
 */

方法二：对应思路二

class MinStack {

    Deque<Node> stack;

    public MinStack() {
        stack = new ArrayDeque<>();
    }
    
    public void push(int val) {
        if (stack.isEmpty()) {
            stack.push(new Node(val, val));
        } else {
            stack.push(new Node(val, Math.min(stack.peek().min, val)));
        }
    }
    
    public void pop() {
        if (!stack.isEmpty()) {
            stack.pop();
        }
		throw new RuntimeException("栈中元素为空，此操作非法");
    }
    
    public int top() {
        if (!stack.isEmpty()) {
            return stack.peek().val;
        }
		// 如果报错,可以返回一个异常
        throw new RuntimeException("栈中元素为空，此操作非法");
    }
    
    public int getMin() {
        if (!stack.isEmpty()) {
            return stack.peek().min;
        }
		// 如果报错,可以返回一个异常
        throw new RuntimeException("栈中元素为空，此操作非法");
    }

	// 静态内部类
    private static class Node {
        int val;
        int min;
        public Node(int val, int min) {
            this.val = val;
            this.min = min;
        }
    }
}

/**
 * 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();
 */