P1165 日志分析题解
思路分析
这题是典型的栈问题，三种操作
1、0入栈x
2、1出栈
3、2查询最大值
乍一看很简单，定义一个栈，循环判断三种条件进行操作就行了，但是再一看，诶，也不难！哈哈哈哈哈哈，不开玩笑了，对于我这种菜鸡来说还是有必要写一写的，我当时在做这题的时候就在想怎么找到这个最大值？如果我用一个普通的栈，那我每次查询都需要遍历完整个栈，时间复杂度 O(n)，但 n 最大 20 万，所以我TLE了。。。如果像之前用一个变量记录当前最大值，出栈时，最大值弹出，我是不知道新的最大值是多少的。
例如：
操作：入库 1, 入库 5, 入库 3
当前最大值 = 5出库一次 → 3 被弹出
问题：最大值 5 还在栈里吗？如果在，还是 5
但如果之前是这样的：
入库 1, 入库 5, 入库 5, 入库 2
最大值 = 5出库一次 → 2 被弹出，最大值还是 5
出库一次 → 5 被弹出，此时最大值应该是 5（还剩一个5）
用栈来存储最大值
核心思想：每个元素入库时，同时记录"从栈底到当前位置的最大值"
实际栈: 1 → 5 → 3 → 2
最大值栈: 1 → 5 → 5 → 5
每次查询，直接看最大值栈的顶部即可 O(1)
话不多说，直接上ac代码
#include <iostream> #include <stack> #include <algorithm> using namespace std; int main() { int N; cin >> N; stack<int> stk; // 存放集装箱重量 stack<int> maxStk; // 存放到当前位置的最大值 for (int i = 0; i < N; i++) { int op; cin >> op; if (op == 0) { // 入库 int x; cin >> x; stk.push(x); if (maxStk.empty()) { maxStk.push(x); } else { maxStk.push(max(x, maxStk.top())); } } else if (op == 1) { // 出库 if (!stk.empty()) { stk.pop(); maxStk.pop(); } } else if (op == 2) { // 查询 if (stk.empty()) { cout << 0 << endl; } else { cout << maxStk.top() << endl; } } } return 0; }