XP04-day05
2026-08-16 20:42:03
发布于：广东
106阅读
0回复
0点赞
考试题解
1. stack 栈
stack<int> st;
st.push(x); // 入栈
st.pop(); // 弹出栈顶
st.top(); // 查看栈顶
st.empty(); // 是否为空
st.size(); // 元素个数
特点：
后进先出 LIFO
2. queue 队列
queue<int> q;
q.push(x); // 队尾加入
q.pop(); // 队首删除
q.front(); // 队首
q.back(); // 队尾
q.empty();
q.size();
特点：
先进先出 FIFO
3. deque 双端队列
deque<int> q;
q.push_front(x); // 队首加入
q.push_back(x); // 队尾加入
q.pop_front(); // 队首删除
q.pop_back(); // 队尾删除
q.front(); // 队首
q.back(); // 队尾
q.empty();
q.size();
单调队列最常用：
q.pop_front(); // 删除过期元素
q.pop_back(); // 删除无用元素
q.push_back(i); // 新元素入队
q.front(); // 当前最优值位置
4. priority_queue 优先队列
默认是大根堆：
priority_queue<int> q;
q.push(x);
q.pop();
q.top(); // 最大值
q.empty();
q.size();
小根堆：
priority_queue<int,vector<int>,greater<int> > q;
此时：
q.top(); // 最小值
最简口诀：
stack：top
queue：front / back
deque：front / back，两边都能删加
priority_queue：top，自动维护最大/最小
PTA-Little Bird
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int INF=1e9;
int n,q;
int d[N],dp[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>d[i];
cin>>q;
while(q--){
int k;
cin>>k;
for(int i=1;i<=n;i++)dp[i]=INF;
dp[1]=0;
deque<int> q;
q.push_back(1);
for(int i=2;i<=n;i++){
// 超出 [i-k,i-1] 的位置出队
while(q.size()&&q.front()<i-k)q.pop_front();
// 队首就是当前最优前驱
int j=q.front();
dp[i]=dp[j];
if(d[i]>=d[j])dp[i]++;
// 维护 dp 从小到大
// dp 相同时，高度从大到小
while(q.size()&&(dp[q.back()]>dp[i]||(dp[q.back()]==dp[i]&&d[q.back()]<=d[i])))q.pop_back();
q.push_back(i);
}
cout<<dp[n]<<"\n";
}
return 0;
}
琪露诺
暴力dp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
const ll INF=4e18;
int n,l,r;
ll a[N],dp[N];
int main(){
cin>>n>>l>>r;
for(int i=0;i<=n;i++){
cin>>a[i];
dp[i]=-INF;
}
dp[0]=0;
// dp[i]：到达 i 点能够获得的最大冰冻指数
for(int i=1;i<=n;i++){
// 上一个位置 j 必须满足 i-r <= j <= i-l
for(int j=max(0,i-r);j<=i-l;j++){
if(dp[j]==-INF)continue;
dp[i]=max(dp[i],dp[j]+a[i]);
}
}
ll ans=-INF;
// 如果从 0 就可以直接跳到对岸
if(r>n)ans=0;
// 从 i 再跳一步可以超过 n
for(int i=1;i<=n;i++){
if(i+r>n)ans=max(ans,dp[i]);
}
cout<<ans;
return 0;
}
单调队列dp优化
//假设现在在 i 点 可以从[i-R,i-L] 转移过来
// [L,R] = [1,2] 5 [i-R]
#include<bits/stdc++.h>
using namespace std;
long long dp[200010],a[200010];
int n,l,r;
int main(){
cin>>n>>l>>r;
for(int i=0;i<=n;i++){
cin>>a[i];
dp[i] = -1e18;
}
deque<long long> q;
dp[0] = 0;
// 1 2 3 4 5
long long ans = -1e18;
for(int i=1;i<=n;i++){
while(q.size() && q.front()<i-r)q.pop_front();
if(i-l>=0){
while(q.size() && dp[q.back()] <= dp[i-l])q.pop_back();
q.push_back(i-l);
if(q.size())dp[i] = dp[q.front()] + a[i];
}
if(i+r>n)ans=max(ans,dp[i]);
}
cout<<ans;
return 0;
}
单调队列笔记
1. 作用
求长度为 的滑动窗口中的最小值或最大值。
当前窗口：
2. 核心思想
deque 中存下标。
求最小值时，维护：
队首 → 队尾
小 → 大
所以：
a[q.front()]
就是当前窗口最小值。
3. 三步操作
// 1. 删除已经离开窗口的元素
while(q.size()&&q.front()<i-k+1)q.pop_front();
// 2. 删除队尾无用元素
while(q.size()&&a[i]<=a[q.back()])q.pop_back();
// 3. 当前元素入队
q.push_back(i);
窗口形成后：
if(i>=k)cout<<a[q.front()]<<" ";
4. 为什么队尾可以删除
假设队尾是 5，当前来了 3：
5 3
3：
- 比
5小； - 比
5更晚离开窗口。
所以以后 5 不可能成为最小值，可以直接删除。
5. 完整代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,k;
int a[N];
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
deque<int> q;
for(int i=1;i<=n;i++){
while(q.size()&&q.front()<i-k+1)q.pop_front();
while(q.size()&&a[i]<=a[q.back()])q.pop_back();
q.push_back(i);
if(i>=k)cout<<a[q.front()]<<" ";
}
return 0;
}
6. 求最大值
最小值：
while(q.size()&&a[i]<=a[q.back()])q.pop_back();
最大值改成：
while(q.size()&&a[i]>=a[q.back()])q.pop_back();
7. 复杂度
每个元素最多入队、出队一次。
时间复杂度：
空间复杂度：
8. 口诀
队首过期 → 删队首
队尾不优 → 删队尾
当前元素 → 入队
队首元素 → 当前答案
最小值：维护单调递增。
最大值：维护单调递减。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,k;
int a[N];
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
deque<int> q,q2;
// 求最小值
//[1,k]
for(int i=1;i<=n;i++){
// [i-k+1,i]
while(q.size() && q.front()<i-k+1)q.pop_front();
//无用的元素都删除
while(q.size() && a[i]<=a[q.back()])q.pop_back();
q.push_back(i);
if(i>=k)cout<<a[q.front()]<<" ";
}
cout<<"\n";
// 求最大值
for(int i=1;i<=n;i++){
while(q2.size()&&q2.front()<i-k+1)q2.pop_front();
while(q2.size()&&a[q2.back()]<=a[i])q2.pop_back();
q2.push_back(i);
if(i>=k)cout<<a[q2.front()]<<" ";
}
return 0;
}
单调栈学习笔记
一、什么是单调栈
单调栈本质还是一个普通的 stack，只不过我们通过不断弹栈，使栈中的元素保持单调。
常见两种：
单调递增栈：
栈底 → 栈顶
小 → 大
单调递减栈：
栈底 → 栈顶
大 → 小
单调栈最常解决的问题：
- 左边第一个比我大的元素
- 左边第一个比我小的元素
- 右边第一个比我大的元素
- 右边第一个比我小的元素
- 柱状图最大矩形
- 统计某个数作为区间最大值、最小值的贡献
二、核心理解
不要死记“维护单调性”。
可以理解成：
栈里面存的都是“还没有找到答案的人”。
例如要求：
右边第一个比自己大的元素。
当前来了一个新元素 a[i]。
如果：
a[i]>a[st.top()]
说明当前元素就是栈顶元素一直等待的答案。
所以：
ans[st.top()]=i;
st.pop();
继续看新的栈顶。
直到栈顶不比当前元素小，再把当前元素入栈等待自己的答案。
三、右边第一个比我大的元素
例如：
位置：1 2 3 4 5
数值：1 4 2 3 5
答案：
位置1：右边第一个更大是位置2
位置2：右边第一个更大是位置5
位置3：右边第一个更大是位置4
位置4：右边第一个更大是位置5
位置5：不存在
所以：
2 5 4 5 0
模拟过程
当前 1
栈：1
当前 4
4 > 1
ans[1]=2
栈：4
当前 2
2 < 4
栈：4 2
当前 3
3 > 2
ans[3]=4
栈：4 3
当前 5
5 > 3
ans[4]=5
5 > 4
ans[2]=5
栈：5
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n;
long long a[N];
int ans[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
stack<int> st;
for(int i=1;i<=n;i++){
while(st.size()&&a[st.top()]<a[i]){
ans[st.top()]=i;
st.pop();
}
st.push(i);
}
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
return 0;
}
四、为什么栈是单调的
还是求：
右边第一个比我大的元素。
代码：
while(st.size()&&a[st.top()]<a[i]){
st.pop();
}
st.push(i);
所有比当前 a[i] 小的元素都会被弹掉。
所以最后留下来的栈顶一定满足：
a[st.top()] >= a[i]
然后再把 i 放进去。
因此栈中的值自然形成：
栈底 → 栈顶
大 → 小
也就是一个单调递减栈。
所以：
不是为了单调而单调，而是“已经找到答案的人被弹掉”，剩下的人自然形成了单调性。
五、四种经典模板
1. 右边第一个更大
从左往右扫：
stack<int> st;
for(int i=1;i<=n;i++){
while(st.size()&&a[st.top()]<a[i]){
ans[st.top()]=i;
st.pop();
}
st.push(i);
}
2. 右边第一个更小
stack<int> st;
for(int i=1;i<=n;i++){
while(st.size()&&a[st.top()]>a[i]){
ans[st.top()]=i;
st.pop();
}
st.push(i);
}
3. 左边第一个更大
当前元素把比自己小的全部弹掉。
弹完以后，栈顶就是左边第一个更大的元素。
stack<int> st;
for(int i=1;i<=n;i++){
while(st.size()&&a[st.top()]<=a[i])st.pop();
if(st.size())ans[i]=st.top();
else ans[i]=0;
st.push(i);
}
4. 左边第一个更小
stack<int> st;
for(int i=1;i<=n;i++){
while(st.size()&&a[st.top()]>=a[i])st.pop();
if(st.size())ans[i]=st.top();
else ans[i]=0;
st.push(i);
}
六、怎么判断扫描方向
可以简单记：
求右边的答案
通常：
从左往右扫
当前元素帮助前面的元素得到答案。
求左边的答案
通常：
从左往右扫
先弹掉不合法元素，然后直接看：
st.top()
就是左边最近满足条件的位置。
七、为什么是
虽然代码里面有：
for(...)
while(...)
看起来像 。
但是每一个元素：
最多入栈一次
最多出栈一次
例如：
1 4 2 3 5
元素 1 被弹掉以后，就永远不会重新进入栈。
所以所有 while 加起来最多弹 次。
因此总时间复杂度：
空间复杂度：
八、经典应用：发射站
如果一个发射站的能量，会被左右两边最近且比它高的发射站接收。
当前处理第 i 个位置：
while(st.size()&&h[st.top()]<h[i]){
ans[i]+=v[st.top()];
st.pop();
}
被弹出的元素：
当前
i就是它右边第一个比它高的位置。
弹完以后：
if(st.size())ans[st.top()]+=v[i];
此时栈顶：
就是
i左边第一个比它高的位置。
模板：
stack<int> st;
for(int i=1;i<=n;i++){
while(st.size()&&h[st.top()]<h[i]){
ans[i]+=v[st.top()];
st.pop();
}
if(st.size())ans[st.top()]+=v[i];
st.push(i);
}
九、区间最大值贡献
很多题会求：
所有子区间最大值之和。
对于每个 a[i]，找到：
L = 左边第一个比它大的位置
R = 右边第一个比它大或等于的位置
那么以 a[i] 作为最大值的区间数量：
贡献就是：
(i-L)*(R-i)*a[i]
最小值同理。
十、相等元素的注意事项
如果数组中可能有相等元素：
2 2 2
左右两边都使用严格比较，可能导致同一个区间被重复统计。
做贡献题时通常需要：
一边严格
一边非严格
例如最大值：
左边：严格大于
右边：大于等于
最小值：
左边：严格小于
右边：小于等于
这样可以保证每个区间只归属于一个位置。
十一、单调栈核心口诀
求右边第一个更大：
当前元素来了
↓
比我小的全部弹掉
↓
被弹掉的人：
我就是它右边第一个更大
↓
我自己入栈等待
再记一句：
栈里留下的是还没有找到答案的人。
这就是单调栈最核心的思想。
十二、常见错误
1. 栈里建议存下标
推荐：
stack<int> st;
存位置，比较时：
a[st.top()]
这样既能得到值，也能得到下标。
2. 注意严格和非严格
<
<=
>
>=
在有重复元素时区别很大。
3. 不存在时答案通常为
全局数组默认：
ans[i]=0;
所以没有找到答案的元素可以不用额外处理。
4. while 不是 if
必须：
while(st.size()&&...)
因为一个当前元素可能同时解决很多前面的元素。
例如：
4 3 2 6
当前 6 可以一次弹：
2
3
4
所以一定是 while。
总结
单调栈主要解决：
某个元素左边或右边，第一个比它大 / 小的位置。
最重要的理解：
栈中元素
=
还没有找到答案的元素
当前元素出现后：
能解决谁
→ 谁出栈
解决不了谁
→ 谁继续等待
最后自己入栈
→ 等待未来的答案
每个元素最多入栈、出栈一次，因此时间复杂度为 。
平衡数组
单调栈
发射站
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int a[N],b[N],n,ans[N];
int main(){
cin>>n;
// a高度 b能量
for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
stack<int> s;
for(int i=n;i>=1;i--){
//a[i] 找后面第一个比他大元素
while(s.size() && a[i]>=a[s.top()])s.pop();
if(s.size())ans[s.top()]+=b[i];
s.push(i);
}
while(s.size())s.pop();
for(int i=1;i<=n;i++){
//a[i] 找前面第一个比他大元素
while(s.size() && a[i]>=a[s.top()])s.pop();
if(s.size())ans[s.top()]+=b[i];
s.push(i);
}
int res = 0;
for(int i=1;i<=n;i++)res=max(ans[i],res);
cout<<res;
return 0;
}
有帮助，赞一个