最小栈 | 秋招知识库

方法一：额外保存前缀最小值

引入

给你一个数组 $nums$ ，如何计算每个前缀的最小值？

定义 $preMin [i]$ 表示 $nums [0]$ 到 $nums [i]$ 的最小值。

这可以从左到右计算：

$preMin [0] = nums [0]$ 。
$preMin [1] = min (nums [0], nums [1])$ 。
$preMin [2] = min (nums [0], nums [1], nums [2]) = min (preMin [1], nums [2])$ 。
$preMin [3] = min (nums [0], nums [1], nums [2], nums [3]) = min (preMin [2], nums [3])$ 。
……

一般地，我们有

preMin [i] = min (preMin [i - 1], nums [i])

回到本题

把 $nums$ 视作栈，本题相当于在 $nums$ 的末尾动态地添加/删除元素。

栈中除了保存添加的元素，还保存前缀最小值。（栈中保存的是 pair）
添加元素：设当前栈的大小是 $n$ 。添加元素 $val$ 后，额外维护 $preMin [n] = min (preMin [n - 1], val)$ ，其中 $preMin [n - 1]$ 是添加 $val$ 之前，栈顶保存的前缀最小值。
删除元素：弹出栈顶即可。

细节

一开始栈为空（ $n = 0$ ），添加 $val$ 时，我们没有对应的 $preMin [n - 1]$ 。需要特判栈为空的情况吗？

不需要。初始化的时候，在栈底加一个 $\infty$ 哨兵，作为 $preMin [- 1]$ 。

注：题目保证 $pop, top, getMin$ 都是在非空栈上操作的。

Python 解法1C++ 解法1

python

class MinStack:
    def __init__(self):
        # 这里的 0 写成任意数都可以，反正用不到
        self.st = [(0, inf)]  # 栈底哨兵

    def push(self, val: int) -> None:
        self.st.append((val, min(self.st[-1][1], val)))

    def pop(self) -> None:
        self.st.pop()

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

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

cpp

// C++ 版待补充

C++ 解法2

cpp

class MinStack {
    stack<pair<int, int>> st;

public:
    MinStack() {
        // 添加栈底哨兵 INT_MAX
        // 这里的 0 写成任意数都可以，反正用不到
        st.emplace(0, INT_MAX);
    }

    void push(int val) {
        st.emplace(val, min(getMin(), val)); 
    }

    void pop() {
        st.pop();
    }

    int top() {
        return st.top().first;
    }

    int getMin() {
        return st.top().second;
    }
};

复杂度分析

时间复杂度：所有操作均为 $O (1)$ 。注：严格地说， $push$ 是均摊 $O (1)$ 。
空间复杂度： $O (q)$ 。其中 $q$ 是 $push$ 调用的次数。最坏情况下，只有 $push$ 操作，需要 $O (q)$ 的空间保存元素。

方法二：保存差值

进阶问题：如果不允许额外保存前缀最小值，栈中只能保存整数（不能保存数对），怎么做？

如果栈中保存的是 $val$ 与前缀最小值的差值，那么只要我们能实时维护前缀最小值，就能通过差值还原 $val$ 。

例如依次插入 $val = 5, 6, 8, 1, 2$ ，计算过程如下表。

如何阅读下表：

表格中的差值等于插入的 $val$ 减去插入之前的最小值。
$push (val)$ 从上到下阅读， $top$ 和 $pop$ 从下到上阅读。

$push (val)$	最小值	差值	$top$	$pop$
$ $	$\infty$	$ $	$ $	$ $
$5$	$5$	$- \infty$	最小值	最小值增加 $\infty$
$6$	$5$	$1$	最小值 $+$ 差值	最小值不变
$8$	$5$	$3$	最小值 $+$ 差值	最小值不变
$1$	$1$	$- 4$	最小值	最小值增加 $4$
$2$	$1$	$1$	最小值 $+$ 差值	最小值不变

一般地：

初始化前缀最小值 $mn = \infty$ 。
$push (val)$ ：先把 $(val - mn)$ 入栈，再更新 $mn$ 为 $min (mn, val)$ 。
$top$ ：返回 $mn + max (栈顶, 0)$ 。如果栈顶大于 $0$ ，说明 $val$ 比 $mn$ 多一个栈顶的值；否则 $val$ 就是 $mn$ 。
$pop$ ：把 $mn$ 减少 $min (栈顶, 0)$ 。如果栈顶小于 $0$ ，这会把 $mn$ 增大；否则 $mn$ 不变。
$getMin$ ：返回 $mn$ 即可。

代码实现时，为避免溢出，需要用 64 位整数。

注：题目保证 $pop, top, getMin$ 都是在非空栈上操作的。

Python 解法3C++ 解法3

python

class MinStack:
    def __init__(self):
        self.st = []
        self.mn = inf

    def push(self, val: int) -> None:
        # 栈中保存 val - 之前的最小值
        self.st.append(val - self.mn)
        self.mn = min(self.mn, val)

    def pop(self) -> None:
        # 如果栈顶是负数，增大 mn，否则不变
        self.mn -= min(self.st.pop(), 0)

    def top(self) -> int:
        # 如果栈顶是正数，说明实际的 val 比 mn 大，否则 val 等于 mn
        return self.mn + max(self.st[-1], 0)

    def getMin(self) -> int:
        return self.mn

cpp

// C++ 版待补充

C++ 解法4

cpp

class MinStack {
    stack<long long> st;
    long long mn = LLONG_MAX / 2; // 避免 val - mn 溢出

public:
    void push(int val) {
        // 栈中保存 val - 之前的最小值
        st.push(val - mn);
        mn = min(mn, 1LL * val);
    }

    void pop() {
        // 如果栈顶是负数，增大 mn，否则不变
        mn -= min(st.top(), 0LL);
        st.pop();
    }

    int top() {
        // 如果栈顶是正数，说明实际的 val 比 mn 大，否则 val 等于 mn
        return mn + max(st.top(), 0LL);
    }

    int getMin() {
        return mn;
    }
};

复杂度分析

时间复杂度：所有操作均为 $O (1)$ 。注：严格地说， $push$ 是均摊 $O (1)$ 。
空间复杂度： $O (q)$ 。其中 $q$ 是 $push$ 调用的次数。最坏情况下，只有 $push$ 操作，需要 $O (q)$ 的空间保存元素。

变形题

改成队列（queue）， $getMin$ 返回队列中的最小元素。
改成双端队列（deque）， $getMin$ 返回双端队列中的最小元素。

解答：[Tutorial] Minimum Deque。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

方法一：额外保存前缀最小值 ​

引入 ​

回到本题 ​

细节 ​

复杂度分析 ​

方法二：保存差值 ​

复杂度分析 ​

变形题 ​

分类题单 ​

方法一：额外保存前缀最小值

引入

回到本题

细节

复杂度分析

方法二：保存差值

复杂度分析

变形题

分类题单