155. 最小栈

✨核心逻辑

本题采用 辅助栈（双栈） 的策略：

双栈结构：维护两个栈，一个是正常记录元素顺序的 数据栈（dataStack），另一个是专门用来记录最小值的 最小栈（minStack）。
入栈逻辑（push）：数据栈直接压入新元素；最小栈只有在栈为空或者新元素小于等于当前最小栈栈顶元素时才压入。注意必须包含 <= 的情况，否则当存在多个相同的最小值时，后续出栈会丢失最小值记录。
出栈逻辑（pop）：数据栈正常弹出栈顶元素；如果数据栈弹出的元素恰好等于当前最小栈的栈顶元素（即弹出的正好是当前的最小值），则最小栈也要同步弹出。
获取操作（top 和 getMin）：top() 直接返回数据栈的栈顶元素；getMin() 直接返回最小栈的栈顶元素，保证获取最小值的操作复杂度为 O(1)。

🔥代码实现（含详细变量注释）

public class MinStack {    
    // 1. 定义两个成员变量（在类下面，而不是在构造函数里面）
    private Deque<Integer> dataStack; // dataStack：数据栈，用于正常存放所有入栈的元素
    private Deque<Integer> minStack;  // minStack：最小栈，用于同步记录当前数据栈中的最小元素

    public MinStack() {
        // 2. 在构造函数里初始化双端队列（使用 ArrayDeque 作为栈的实现，比旧版 Stack 性能更好）
        dataStack = new ArrayDeque<>();
        minStack = new ArrayDeque<>();
    }
    
    public void push(int val) {
        // 数据栈正常放入元素
        dataStack.push(val);
        // 如果最小栈为空，或者新来的值小于等于当前最小值，最小栈也同步放入
        // (注意：这里一定要用 <=，保证如果有重复的最小值，后续 pop 时能同步处理掉)
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }
    
    public void pop() {
        // 取出数据栈要弹出的值
        int val = dataStack.pop();
        // 如果弹出的值恰好等于当前记录的最小值，说明原有的最小值被移除了
        // 因此最小栈也要同步弹出，恢复到前一个最小值状态
        if (val == minStack.peek()) {
            minStack.pop();
        }
    }
    
    public int top() {
        // 返回数据栈的栈顶元素
        return dataStack.peek();
    }
    
    public int getMin() {
        // 最小栈的栈顶元素，永远代表当前数据栈里的最小值
        return minStack.peek();
    }
}

⏱️复杂度分析
- 时间复杂度：O(1)，所有方法（push、pop、top、getMin）均只涉及基本数据结构的栈顶元素操作，不涉及循环遍历，消耗常数时间。
- 空间复杂度：O(N)，其中 N 是栈内元素的个数。在最坏情况下（即 push 的元素是严格递减的），辅助最小栈 minStack 的大小会与数据栈 dataStack 的大小一致，额外占用 O(N) 的空间。