剑指 Offer 30. 包含min函数的栈

题目

剑指 Offer 30. 包含min函数的栈

栈的特点：先进后出，后进先出。

题解

数据栈和辅助栈

• 0，声明一个栈为stack1，另一个栈为stack2
• 1，push(-2)到stack1，此时该栈中的最小值是-2，因此stack2 push进-2
• 2，push(0)到stack1，此时该栈中的最小值是-2，因此stack2 再次push进-2
• 3，push(-3)到stack1，此时该栈中的最小值是-3，因此stack2 push进-3

此时两个栈中的值为：

• 4，此时调用最小栈的min，从stack2中pop最小值为-3
• 5，调用最小栈的pop操作，同时从stack1和stack2中把-3弹出去（删除掉）

此时两个栈中的值为：

--------------------------------------------------------
               栈顶
 0                                  -2
 -2                                 -2
               栈底
stack1                            stack2
-------------------------------------------------------

• 6，执行最小栈的top操作，从stack1 获取出此时的栈顶元素0
• 7，执行最小栈的min操作，从stack2 获取出此时的栈顶元素-2，也就是此时最小栈里的最小值为-2

//Java
class MinStack {
    // 创建两个栈
    // 创建stack1，用来作为数据栈
    Stack<Integer> stack1;

    // 创建stack2，用来作为辅助栈
    Stack<Integer> stack2;

    /** initialize your data structure here. */
    public MinStack() {
        // 初始化 stack1
        stack1 = new Stack<Integer>();

        // 初始化 stack2
        stack2 = new Stack<Integer>();
    }
    // 最小栈的压入操作
    public void push(int x) {
        // 数据栈 stack1直接压入 x
        stack1.push(x);

        // 如果辅助栈 stack2为空，可以直接压入 x
        // 此时，由于只有一个元素，stack2中的【栈顶元素】就是 stack1 中的 【最小元素】
        if (stack2.isEmpty()){
            // stack2 直接压入x
            stack2.push(x);
        } else {
            // 辅助栈 stack2 不为空
            if (stack2.peek() >= x) {
                // 如果辅助栈 stack2 的栈顶元素大于等于x，可以把 x 压入到 stack2 中
                stack2.push(x);
            } else {
                // 如果辅助栈 stack2 的栈顶元素小于x，不可以把 x 压入到 stack2 中
                // 所以将辅助栈原先的【栈顶元素】压入即可
                stack2.push(stack2.peek());
            }
        }
    }
    
    public void pop() {
        // 数据栈 stack1 直接pop
        stack1.pop();
        // 数据栈 stack2 直接pop
        stack2.pop();
    }
    
    public int top() {
        // 返回数据栈 stack1 的栈顶元素
        return stack1.peek();
    }
    
    public int min() {
        // 由于 stack2的【栈顶元素】是 stack1的【最小元素】，所以直接返回stack2的栈顶元素即可
        return stack2.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

leetcode-cn执行：

执行用时：14 ms, 在所有 Java 提交中击败了22.98%的用户
内存消耗：43.7 MB, 在所有 Java 提交中击败了17.84%的用户