【题目来源】
https://www.luogu.com.cn/problem/P1165
【题目描述】
M 海运公司最近要对旗下仓库的货物进出情况进行统计。目前他们所拥有的唯一记录就是一个记录集装箱进出情况的日志。该日志记录了两类操作：第一类操作为集装箱入库操作，以及该次入库的集装箱重量；第二类操作为集装箱的出库操作。这些记录都严格按时间顺序排列。集装箱入库和出库的规则为先进后出，即每次出库操作出库的集装箱为当前在仓库里所有集装箱中最晚入库的集装箱。
出于分析目的，分析人员在日志中随机插入了若干第三类操作――查询操作。分析日志时，每遇到一次查询操作，都要报告出当前仓库中最大集装箱的重量。
【输入格式】
包含 N+1 行：
第一行为一个正整数 N，对应于日志内所含操作的总数。
接下来的 N 行，分别属于以下三种格式之一：
格式 1：0 X，表示一次集装箱入库操作，正整数 X 表示该次入库的集装箱的重量。
格式 2：1，表示一次集装箱出库操作，（就当时而言）最后入库的集装箱出库。
格式 3：2，表示一次查询操作，要求分析程序输出当前仓库内最大集装箱的重量。
当仓库为空时你应该忽略出库操作，当仓库为空查询时你应该输出 0。
【输出格式】
输出行数等于日志中查询操作的次数。每行为一个整数，表示查询结果。
【输入样例】
13
0 1
0 2
2
0 4
0 2
2
1
2
1
1
2
1
2
【输出样例】
2
4
4
1
0
【数据范围】
对于 20% 的数据，有 N≤10；
对于 40% 的数据，有 N≤1000；
对于 100% 的数据，有 1≤N≤200000，1≤X≤10^8。
【算法分析】
●双栈（极值栈）是 “空间换时间” 的经典技巧
（1）stk[maxn]：模拟普通栈，存储所有压入的元素，top 是普通栈的栈顶指针（初始默认为 0，表示空栈）。
（2）imx[maxn]：模拟 “最大值栈”，存储的是每一次出现 “新的更大值” 时的那个最大值，p 是最大值栈的栈顶指针（初始默认为 0，表示空栈）。
（3）这里的关键：imx 栈不是存储每个位置的最大值，而是只存储 “递增的最大值序列”，这样可以节省空间，且查询时直接取栈顶即可。
【算法代码】
#include <bits/stdc++.h> using namespace std; const int maxn=2e5+5; int stk[maxn],top; //stack 1 int imx[maxn],p; //stack 2 int op,x,T; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>T; while(T--) { cin>>op; if(op==0) { cin>>x; stk[++top]=x; if(x>imx[p]) imx[++p]=x; } else if(op==1) { if(top) { if(stk[top]==imx[p]) p--; top--; } } else cout<<imx[p]<<"\n"; } return 0; } /* in: 13 0 1 0 2 2 0 4 0 2 2 1 2 1 1 2 1 2 out: 2 4 4 1 0 */
【参考文献】
https://www.luogu.com.cn/problem/solution/P1165
https://www.cnblogs.com/jess1ca1o0g3/p/18275359
