最小栈

---

题目链接

https://leetcode.cn/problems/min-stack/

思路分析

新增一个 minStack，和 data 栈同步更新（压入一个元素时），minStack 的栈顶记录了当前栈中元素的最小值

（1）当两个栈为空时，同步压入

（2）当前压入的元素 <= minStack.peek（），则 minStack 中压入当前元素

（3）当前压入元素 > minStack.peek（），则 minStack 中压入 minStack.peek（），即重复压入最小栈的栈顶

当元素出栈时，两个栈同步执行 pop（）操作

代码实现

内部实现

class MinStack {
    public Stack<Integer> data;
    public Stack<Integer> min;

    public MinStack() {
        data = new Stack<Integer>();
        min = new Stack<Integer>();
    }

    public void push(int val) {
        data.push(val);
        if (min.isEmpty() || val <= min.peek()) {
            min.push(val);
        } else {
            // !min.isEmpty() && val > min.peek()
            min.push(min.peek());
        }
    }

    // pop 操作注意是同步执行的
    public void pop() {
        data.pop();
        min.pop();
    }

    public int top() {
        return data.peek();
    }

    public int getMin() {
        return min.peek();
    }
}

数组实现

class MinStack {
    // leetcode的数据在测试时，同时在栈里的数据不超过这个值
    // 这是几次提交实验出来的，哈哈
    // 如果leetcode补测试数据了，超过这个量导致出错，就调大
    public final int MAXN = 8001;

    public int[] data;
    public int[] min;
    int size;

    public MinStack() {
        data = new int[MAXN];
        min = new int[MAXN];
        size = 0;
    }

    public void push(int val) {
        // 首先处理 data 栈，之后再对 min 栈进行处理
        data[size] = val;
        if (size == 0 || val <= min[size - 1]) {
            min[size] = val;
        } else {
            min[size] = min[size - 1];
        }
        size++;
    }

    // 两个栈的大小都是 size，size-- 即同步了两个栈的 pop 操作
    public void pop() {
        size--;
    }

    public int top() {
        return data[size - 1];
    }

    public int getMin() {
        return min[size - 1];
    }
}