日志分析(Log Analysis) 题解

思路分析

维护一个前缀最大值辅助栈 mx[]：当集装箱 X 入栈时，mx[top] = max(mx[top - 1], X)（其中 mx[0] = 0）；出栈时若 top > 0 则 --top；查询时直接输出 mx[top]（空栈时 top = 0，恰好输出 0）。单次操作 $O(1)$，总时间复杂度 $O(N)$。

参考代码

#include <algorithm>
#include <iostream>
using namespace std;

const int MX = 200005;
int mx[MX];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    int top = 0;
    mx[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        int op;
        cin >> op;
        if (op == 0)
        {
            int x;
            cin >> x;
            ++top;
            mx[top] = max(mx[top - 1], x);
        }
        else if (op == 1)
        {
            if (top > 0) --top;
        }
        else
        {
            cout << mx[top] << "\n";
        }
    }
    return 0;
}