【LeetCode 热题 100】155. 最小栈

Problem: 155. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

整体思路

这段代码旨在实现一个经典的特殊数据结构：最小栈 (Min Stack)。这个数据结构除了支持常规栈的 push、pop 和 top 操作外，还必须支持一个 getMin 操作，该操作能够以 常数时间 O(1) 返回栈中当前的最小元素。

该算法的核心思想是，不只在栈中存储元素值本身，而是 将每个元素与其“当时”的栈内最小值绑定在一起存储。

1. 数据结构选择：

   • 算法选择了一个双端队列 Deque<int[]> 并将其用作栈。
   • 关键在于，栈中存储的不是单个整数，而是一个大小为 2 的整型数组 int[]。这个数组被设计成一个元组（pair）：{value, current_minimum}。
     • pair[0] 存储的是被 push 进栈的实际值 val。
     • pair[1] 存储的是当这个 val 被压入时，栈内所有元素（包括 val）的最小值。

2. 核心操作逻辑：

   • push(val): 当一个新值 val 被推入栈时，算法会创建一个新的元组。新元组的第二部分（current_minimum）通过比较 val 和 上一个状态的最小值（即当前栈顶元组的第二部分 getMin()）来确定。这样，每个层级的栈都“知道”自己及以下所有元素的最小值。
   • getMin(): 由于每个状态都保存了到它为止的最小值，获取整个栈的最小值就变得非常简单：只需查看当前栈顶元组的第二部分 st.peek()[1] 即可。这是一个 O(1) 操作。
   • top(): 获取栈顶元素的值，同样只需查看当前栈顶元组的第一部分 st.peek()[0]。
   • pop(): 弹出栈顶元组。这个操作非常巧妙，因为当一个元组被弹出后，新暴露出的栈顶元组中保存的最小值，就自动地变回了上一个状态的最小值，无需任何额外计算。

3. 初始化处理：

   • 构造函数中 st.push(new int[]{0, Integer.MAX_VALUE}); 的操作是一个哨兵节点（Sentinel Node）。它的目的是简化 push 操作的逻辑。通过预置一个最小值为 Integer.MAX_VALUE 的节点，第一次调用 push 时，Math.min(getMin(), val) 就能自然地得到 val 作为第一个真正的最小值，从而避免了在 push 方法中写 if (st.isEmpty()) 的特殊判断。

完整代码

/**
 * 一个支持在常数时间内检索到最小元素的栈。
 */
class MinStack {
    // 使用 Deque 作为栈的底层实现。
    // 存储的是一个大小为2的数组，格式为 {value, current_minimum}。
    private final Deque<int[]> st = new ArrayDeque<>();

    /**
     * 构造函数，初始化最小栈。
     */
    public MinStack() {
        // 推入一个哨兵节点或初始节点。
        // Integer.MAX_VALUE 确保第一个被推入的真实元素的最小值就是它自身。
        // 这样可以避免在 push 方法中对空栈进行特殊处理。
        st.push(new int[]{0, Integer.MAX_VALUE});
    }
    
    /**
     * 将元素 val 推入栈中。
     * @param val 要推入的元素值
     */
    public void push(int val) {
        // 创建一个新的元组 {val, min(当前最小值, val)}。
        // getMin() 会返回上一个状态的最小值。
        // 将新值与上一个状态的最小值比较，得到新的当前最小值。
        st.push(new int[]{val, Math.min(getMin(), val)});
    }
    
    /**
     * 删除栈顶的元素。
     */
    public void pop() {
        // 直接弹出栈顶的元组 {value, current_minimum}。
        // 栈的状态（包括最小值）会自动恢复到上一个状态。
        st.pop();
    }
    
    /**
     * 获取栈顶元素。
     * @return 栈顶元素的值
     */
    public int top() {
        // 栈顶元组的第一个元素 [0] 存储的是实际值。
        return st.peek()[0];
    }
    
    /**
     * 在常数时间内检索到栈中的最小元素。
     * @return 栈中的最小元素值
     */
    public int getMin() {
        // 栈顶元组的第二个元素 [1] 存储的是到当前状态为止的最小值。
        return st.peek()[1];
    }
}

时空复杂度

时间复杂度：O(1)

1. push(val): 该操作包括 getMin() (即 peek)、Math.min 和 st.push()。对于 ArrayDeque，这些都是 O(1) 的均摊时间复杂度。
2. pop(): st.pop() 是 O(1) 的均摊时间复杂度。
3. top(): st.peek() 是 O(1) 的时间复杂度。
4. getMin(): st.peek() 是 O(1) 的时间复杂度。

综合分析：
该数据结构的所有公开操作（push, pop, top, getMin）都具有 O(1) 的时间复杂度，满足了设计要求。

空间复杂度：O(N)

1. 主要存储开销：空间复杂度由栈 st 的大小决定。
2. 空间大小：对于用户推入的每一个元素，我们都在栈中存储一个包含两个整数的数组 int[]。如果栈中有 N 个元素（不包括哨兵节点），那么实际存储了 N 个 int[2] 对象。
3. 综合分析：
   所需的额外空间与栈中元素的数量 N 成线性关系。因此，空间复杂度为 O(N)。

参考灵神