vvrf / DSA.log

问题拆解

要设计一个栈，除了正常的 push、pop、top，还要能在常数时间里拿到当前栈内的最小值。

难点在最后一句。如果每次 getMin 都遍历一遍栈，那是 O(n)，不达标。如果只用一个变量 min 保存全局最小，push 时好维护，可一旦 pop 掉的正是那个最小值，我就不知道“第二小”是谁了——历史信息已经丢了。

问题的核心是：pop 会让最小值“回退”，所以每一层都得记住“到我为止的最小值”是多少。

辅助栈同步保存最小值快照

我再开一个辅助栈 mins，它和主栈同进同出。每次 push 时，压入 当前值 和 已有最小值 中较小的那个——这就是这一层的“最小值快照”。于是 mins 的栈顶永远等于主栈当前的最小值，pop 时两个栈一起弹，快照自动回退。

这题本身是设计题，用 class 来组织状态最自然：

class MinStack {
    private final Deque<Integer> stack = new ArrayDeque<>();
    private final Deque<Integer> mins = new ArrayDeque<>();

    public void push(int val) {
        stack.push(val);
        mins.push(mins.isEmpty() ? val : Math.min(val, mins.peek()));
    }

    public void pop() {
        stack.pop();
        mins.pop();
    }

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

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

class MinStack:
    def __init__(self):
        self.stack = []
        self.mins = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        cur_min = val if not self.mins else min(val, self.mins[-1])
        self.mins.append(cur_min)

    def pop(self) -> None:
        self.stack.pop()
        self.mins.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.mins[-1]

type MinStack struct {
    stack []int
    mins  []int
}

func Constructor() MinStack {
    return MinStack{}
}

func (s *MinStack) Push(val int) {
    s.stack = append(s.stack, val)
    if len(s.mins) == 0 || val < s.mins[len(s.mins)-1] {
        s.mins = append(s.mins, val)
    } else {
        s.mins = append(s.mins, s.mins[len(s.mins)-1])
    }
}

func (s *MinStack) Pop() {
    s.stack = s.stack[:len(s.stack)-1]
    s.mins = s.mins[:len(s.mins)-1]
}

func (s *MinStack) Top() int {
    return s.stack[len(s.stack)-1]
}

func (s *MinStack) GetMin() int {
    return s.mins[len(s.mins)-1]
}

struct MinStack {
    stack: Vec<i32>,
    mins: Vec<i32>,
}

impl MinStack {
    fn new() -> Self {
        MinStack { stack: Vec::new(), mins: Vec::new() }
    }

    fn push(&mut self, val: i32) {
        self.stack.push(val);
        let cur_min = self.mins.last().map_or(val, |&m| m.min(val));
        self.mins.push(cur_min);
    }

    fn pop(&mut self) {
        self.stack.pop();
        self.mins.pop();
    }

    fn top(&self) -> i32 {
        *self.stack.last().unwrap()
    }

    fn get_min(&self) -> i32 {
        *self.mins.last().unwrap()
    }
}

关键在于两个栈严格同步：任何时刻 len(mins) == len(stack)，mins[i] 表示“前 i+1 个元素的最小值”。这样每一次 pop 都精确地把最小值恢复到上一层的状态。

复杂度

指标	复杂度	原因
push / pop / top / getMin	`O(1)`	全是栈顶操作
空间	`O(n)`	辅助栈与主栈等长

可以迁移的模式

某个聚合查询（最小、最大）要求 O(1)，但数据会被撤销；
用“额外一列快照”把历史信息随数据一起保存、一起回退；
空间换时间：多存一份，换来查询不再遍历。

只要操作是“可撤销”的，就想想能不能让每一层自带它需要的答案。