最小栈

题意

设计一个栈，支持 push、pop、top、getMin 四个操作，getMin 要求 $O(1)$ 。

思路

核心思路：栈中每个元素同时保存"当前值"和"截至该层的最小值"。push 时，min 字段取当前值与栈顶 min 的较小值；getMin 直接读栈顶的 min 字段。

这样 pop 后新的栈顶 min 自然就是剩余元素的最小值，无需额外维护。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46#include <bits/stdc++.h>
using namespace std;

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

public:
    void push(int v) {
        st.push({v, st.empty() ? v : min(v, st.top().second)});
    }

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

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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    MinStack ms;
    while (q--) {
        string op;
        cin >> op;
        if (op == "push") {
            int v;
            cin >> v;
            ms.push(v);
        } else if (op == "pop")
            ms.pop();
        else if (op == "top")
            cout << ms.top() << ' ';
        else
            cout << ms.getMin() << ' ';
    }
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35#!/usr/bin/env python3
class MinStack:
    def __init__(self):
        self.st = []

    def push(self, v):
        self.st.append((v, min(v, self.st[-1][1]) if self.st else v))

    def pop(self):
        self.st.pop()

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

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


def main():
    q = int(input())
    ms = MinStack()
    for _ in range(q):
        op = input().split()
        if op[0] == "push":
            ms.push(int(op[1]))
        elif op[0] == "pop":
            ms.pop()
        elif op[0] == "top":
            print(ms.top(), end=" ")
        else:
            print(ms.getMin(), end=" ")


if __name__ == "__main__":
    main()

复杂度

时间复杂度：每个操作 $O(1)$ 。
空间复杂度： $O(n)$ ，每个元素存一对值。

总结

最小栈的关键是"每层同时保存当前值与截至该层的最小值"，使得 pop 后最小值自动更新，不需要辅助栈或重新扫描。

目录

题意

思路

代码

复杂度

总结