日志分析

题意

有三种操作：

0 x：一个重量为 x 的集装箱入库
1：一个集装箱出库
2：查询当前仓库中最大的集装箱重量

仓库遵循先进后出，查询时要输出当前仓库最大重量。

思路

最直接的做法是维护一个栈，查询时重新扫描一遍当前仓库找最大值。

这个版本容易理解：

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#include <bits/stdc++.h>
using namespace std;

int n;
int op, x;
vector<int> st;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    while (n--) {
        cin >> op;
        if (op == 0) {
            cin >> x;
            st.push_back(x);
        } else if (op == 1) {
            if (!st.empty()) {
                st.pop_back();
            }
        } else {
            int ans = 0;
            for (int v : st) {
                ans = max(ans, v);
            }
            cout << ans << '\n';
        }
    }

    return 0;
}

但查询很多时会很慢。

所以我们再维护一个辅助栈 mx，让它的栈顶始终表示“当前仓库里所有集装箱的最大重量”。

入库时：

新集装箱进普通栈 st
辅助栈 mx 记录到当前为止的最大值

出库时：

st 和 mx 同时弹出栈顶

这样查询时直接输出 mx.top() 即可。

代码

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#include <bits/stdc++.h>
using namespace std;

int n;
int op, x;
stack<int> st, mx;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    while (n--) {
        cin >> op;
        if (op == 0) {
            cin >> x;
            st.push(x);
            if (mx.empty()) {
                mx.push(x);
            } else {
                mx.push(max(mx.top(), x));
            }
        } else if (op == 1) {
            if (!st.empty()) {
                st.pop();
                mx.pop();
            }
        } else {
            cout << (mx.empty() ? 0 : mx.top()) << '\n';
        }
    }

    return 0;
}

复杂度

时间复杂度： $O(N)$
空间复杂度： $O(N)$

总结

这题的本质是“栈 + 维护前缀最大值”。

只要把最大值也同步压栈，查询就不需要再扫描整个仓库了。

目录

题意

思路

代码

复杂度

总结