一.单调栈简介
1.1单调栈定义与特性
- 本质：单调栈是一种特殊的栈结构，其内部元素始终保持单调递增或单调递减的顺序。
- 核心规则：当新元素入栈时，会通过弹出破坏单调性的栈顶元素来维持有序性。
- 单调方向：
- 单调递增栈：从栈底到栈顶，元素逐渐变大（例如 [1,3,5,7][1,3,5,7]）。
- 单调递减栈：从栈底到栈顶，元素逐渐变小（例如 [9,6,2,1][9,6,2,1]）。
1.2应用场景
单调栈擅长解决“边界查找”问题，即快速找到数组中某个元素左侧或右侧第一个比它大（或小）的元素
1.3时间复杂度
通过一次遍历O(n)即可解决问题，而暴力解法通常需要 O(n²)。
1.4.原理
例如：使用 10 3 7 4 12 构造一个单调递增栈。
二.例题《发射站》
2.1题目描述
2.2思路
只要求出每个发射站 i 接收到的能量总和 tot[i]，就能求出最大值了。
每个单调栈向左右两个方向发射的能量，只会分别最多被一个发射站接收
因此可以考虑求出每个发射站发射的能量被谁接收，这样就能统计 tot 数组了。
这个过程分两步进行：
求出每个发射站向左发射的能量被谁接收
求出每个发射站向右发射的能量被谁接收
每个发射站向左发射的能量被谁接收：
也就是左边第一个大于当前值的位置
维护一个从栈底到栈顶单调递减的单调栈，从前往后枚举每个放射站并将其高度插入到
单调栈中。
可以发现，在将栈顶所有比 i 的高度小的发射站出栈之后（参考单调栈的插入操作），
新的栈顶就是接收 i 向左发射的能量的发射站。
在维护单调栈的过程中，有些发射站在维护单调性的过程中被出栈了
这些被出栈的发射站是否会接收到 i 后面的发射站发来的能量？
不会，因为 h[i]已经比这些发射站要高了，所以 i 之后的发射站发来的能量就算这些发射站高度符合，也会被 i 挡住，因为 i 也一定符合高度要求。
如何求出每个发射站向右发射的能量被谁接收？ 倒序枚举发射站 n~1，同样维护一个栈底到栈顶单调递减的栈
2.3AC代码
#include<bits/stdc++.h>
using namespace std;
int n,a[1000005],v[1000005],ans[1000005],maxx;
stack<int> st,tmp;
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>v[i];
}
for(int i=1;i<=n;i++){
while(!st.empty()&&a[st.top()]<=a[i]){
st.pop();
}
if(!st.empty()&&a[st.top()]>a[i]){
ans[st.top()]+=v[i];
}
st.push(i);
}
st=tmp;
for(int i=n;i>=1;i--){
while(!st.empty()&&a[st.top()]<=a[i]){
st.pop();
}
if(!st.empty()&&a[st.top()]>a[i]){
ans[st.top()]+=v[i];
}
st.push(i);
}
for(int i=1;i<=n;i++){
if(maxx<ans[i]){
maxx=ans[i];
}
}
cout<<maxx;
return 0;
}2.4AC代码(2)
如果我们一次单调栈操作，直接维护两个信息呢？
得到：
#include<bits/stdc++.h>
using namespace std;
int n,a[1000005],v[1000005],ans[1000005],maxx;
stack<int> st;
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>v[i];
}
for(int i=1;i<=n;i++){
while(!st.empty()&&a[st.top()]<=a[i]){
ans[i]+=v[st.top()];
st.pop();
}
if(!st.empty()){
ans[st.top()]+=v[i];
}
st.push(i);
}
for(int i=1;i<=n;i++){
if(maxx<ans[i]){
maxx=ans[i];
}
}
cout<<maxx;
return 0;
}
