目录
1.单调栈
例题:【模板】单调栈
例题:求和
2.单调队列
例题:滑动窗口
1.单调栈
例题:【模板】单调栈
可以想象出一个柱状图,值越大,这个柱子越高
以此题的样例为例:
第一个数为7,想象一个高度为7的柱子,它的左边没有任何数,所以直接输出-1
然后第二个数为8,想象高度为8的柱子从右往左靠近7,因为7比8小,所以输出7
第三个数为5,5从右往左靠近8,而5比8小,所以8被删除,7大于5,所以7也被删除
此时5左边就没数了,输出-1
第四个数为6大于5,所以输出5
第五个数为7大于6,所以输出6
用栈的方法
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
int a[N],l[N];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
stack<int> stk;
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++)
{
while(stk.size() && stk.top() >= a[i]) stk.pop();
if(stk.empty()) l[i] = -1;
else l[i] = stk.top();
stk.push(a[i]);
}
for(int i = 1; i <= n; i++)
cout << l[i] << ' ';
return 0;
}
例题:求和
这题要对一个数的左边和右边都进行单调栈求比它小的值
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
ll a[N],l[N],r[N];
int stk[N];
int top;//表示栈中元素个数
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++)
{
while(top && a[i] <= a[stk[top]]) top--;
if(top != 0) l[i] = stk[top];
else l[i] = 0;
stk[++top] = i;
}
top = 0;//清空栈
for(int i = n; i >= 1; i--)
{
while(top && a[i] < a[stk[top]]) top--;
if(top != 0) r[i] = stk[top];
else r[i] = n + 1;
stk[++top] = i;
}
ll ans = 0;
for(int i = 1; i <= n; i++) ans += a[i] * (r[i] - i) * (i - l[i]);
cout << ans;
return 0;
}
2.单调队列
例题:滑动窗口
以求窗口内最大值为例,想象一个双端队列,从右边入队,每次入队与原来的队列中的最右边的元素比较大小,如果它的数值更大,那么就从右边pop掉原来队列中最右端的那个数,直到最左边的元素最大为止
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
int a[N];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,k;
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
deque<int> dq;
//求最大值
for(int i = 1; i <= n; i++)
{
while(dq.size() && k <= i - dq.front()) dq.pop_front();
while(dq.size() && a[dq.back()] <= a[i]) dq.pop_back();
dq.push_back(i);
if(i >= k) cout << a[dq.front()] << ' ';
}
dq.clear();
cout << endl;
//求最小值
for(int i = 1; i <= n; i++)
{
//区间合法
while(dq.size() && k <= i - dq.front()) dq.pop_front();
while(dq.size() && a[dq.back()] >= a[i]) dq.pop_back();
dq.push_back(i);
if(i >= k)cout << a[dq.front()] << ' ';
}
return 0;
}