155. 最小栈

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

为了在常数时间内检索到最小元素，我将使用两个栈来实现：一个主栈存储所有元素，一个辅助栈（最小栈）跟踪当前最小值。

import java.util.Stack;

class MinStack {
    private Stack<Integer> stack;    // 主栈，存储所有元素
    private Stack<Integer> minStack; // 最小栈，栈顶始终为当前最小值

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        // 常规入栈操作
        stack.push(val);

        // 如果最小栈为空，或者当前值小于等于最小栈顶元素
        // 将当前值也压入最小栈
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        if (stack.isEmpty()) return;

        int val = stack.pop();

        // 如果弹出的值等于最小栈顶元素，也从最小栈中弹出
        if (val == minStack.peek()) {
            minStack.pop();
        }
    }

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

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

算法解析：

1. 核心思想：

   • 使用两个栈：主栈存储所有元素，最小栈维护当前最小值
   • 最小栈的栈顶元素始终是当前栈中的最小值

2. 操作详解：

   • push(val)：
     • 将值压入主栈
     • 如果最小栈为空或当前值小于等于最小栈顶元素，也将其压入最小栈
     • 注意使用"小于等于"是为了正确处理重复最小值的情况
   • pop()：
     • 从主栈弹出元素
     • 如果弹出的元素等于最小栈顶元素，也从最小栈中弹出
   • top()：
     • 直接返回主栈栈顶元素
   • getMin()：
     • 直接返回最小栈栈顶元素，实现O(1)时间复杂度

3. 复杂度分析：

   • 时间复杂度：所有操作(push、pop、top、getMin)均为O(1)
   • 空间复杂度：O(n)，最坏情况下最小栈需要存储所有元素(当元素按非递增顺序压入时)

4. 关键点：

   • 使用"小于等于"(<=)而非"<"比较，确保重复最小值的正确处理
   • 最小栈只存储需要的最小值，而非所有元素，节约空间