What Is Monotonic Queue
单调队列是一种特殊的队列数据结构，用于维护一定的单调性，通常是单调递增或单调递减。
单调队列的主要特点是，队列中的元素满足特定的单调性要求，使得队列的头部元素（或者尾部元素，取决于具体问题）始终是当前队列中的最大（或最小）值。这种特性使得单调队列可以高效地处理一些需要在不断变化的窗口或序列中找到最大（或最小）值的问题。
Monotonic Queue Can Do What
单调队列在解决一些与窗口和单调性有关的问题时非常有用。以下是一些可以使用单调队列解决的常见问题：
-
滑动窗口最大/最小值： 给定一个数组和一个固定大小的窗口，需要在窗口在数组上滑动的过程中，快速找到每个窗口的最大或最小值。
-
连续子数组的平均值大于阈值的个数： 给定一个数组和一个阈值，找到所有长度为固定值的连续子数组，使得子数组的平均值大于给定的阈值。
-
下一个更大元素： 给定一个数组，对于每个元素，找到在其右边第一个比它大的元素。
这些问题在实际应用中非常常见，而单调队列可以帮助有效解决这些问题，因为它们可以在O(N)的时间复杂度内进行操作，而不是传统的O(N^2)解法。通过维护单调性，单调队列可以在滑动窗口或者数组遍历的过程中高效地找到满足特定条件的元素。
How To Solve These Question
1.滑动窗口最大/最小值
例题：- P1886 滑动窗口 /【模板】单调队列
这题之前使用线段树做的，但是\(nlogn>n\)，1.55s>1.33s。用单调队列整整快了0.22s也不是很多。
当使用单调队列来解决滑动窗口最大/最小值问题时，需要维护一个滑动窗口，以及一个单调递减队列。单调队列用于存储当前窗口内的元素的下标(因为要保持单调队列元素在窗口内)，使得队列的头部始终是窗口内的最值元素。以下是解决滑动窗口最大值问题的方法：
假设有一个数组 \(arr\) 和一个窗口大小 k，我们需要找到每个窗口的最大值。
创建一个单调递减队列 deque，用于存储元素在窗口中的下标。
遍历数组，对于每个元素 \(i\) 进行以下操作：
在每个新元素要加入窗口时，从队列尾部开始，将所有比新元素小的元素下标出队，以保持队列的单调递减性质。
将当前元素下标入队到队列尾部。
对于每个窗口的起始位置，计算窗口内的最大值并记录。
#include<bits/stdc++.h>
using namespace std;
long long n,k,a[1000005];
deque<int>q;//双端队列
int main(){
cin>>n>>k;
for(long long i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
while(!q.empty()&&q.front()<i-k+1){//保证元素在窗口内
q.pop_front();
}
while(!q.empty()&&a[i]<=a[q.back()]){//保证队列内单调递增(队首为区间最小值)
q.pop_back();
}
q.push_back(i);
if(i>=k) cout<<a[q.front()]<<" ";
}
cout<<endl;
while(!q.empty()){//同上
q.pop_front();
}
for(int i=1;i<=n;i++){
while(!q.empty()&&q.front()<i-k+1){
q.pop_front();
}
while(!q.empty()&&a[i]>=a[q.back()]) {
q.pop_back();
}
q.push_back(i);
if(i>=k) cout<<a[q.front()]<<" ";
}
return 0;
}
2.连续子数组的平均值大于阈值的个数
Leetcode 1343
本人没有leetcode账号qwq,只能看题面了
因为滑动窗口长度为k，所以用双端队列即可
#include<bits/stdc++.h>
using namespace std;
int n,a[1000005],k,t,sum=0,ans=0;
deque<int>q;
int main(){
cin>>n>>k>>t;
t=k*t;//平均值>=t -> 子数组数的和>=k*t
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
while(!q.empty()&&q.front()<i-k+1){//超出范围就pop
sum-=a[q.front()];
q.pop_front();
}
q.push_back(i);
sum+=a[i];
if(sum>=t) ans++;//看看可不可以
}
cout<<ans<<endl;
return 0;
}
3.下一个更大元素
例题： P1901 发射站
XJOI上 $ n^{\smash{2}} $ 过百万
假设我们有一个数组 arr，我们要为每个元素找到在其右边第一个比它大的元素。我们可以使用一个单调递减队列来解决这个问题。队列中的元素按照从大到小的顺序排列，当我们遍历数组时，如果当前元素大于队列末尾的元素，那么我们就可以得到队列末尾元素的下一个更大元素。
1.创建一个空的deque
遍历数组，对于每个元素执行以下操作：
如果队列不为空，并且当前元素大于等于队列末尾的元素，那么说明队列末尾的元素找到了下一个更大元素。我们将队列末尾的元素弹出，并将其下标与当前元素建立映射，表示下一个更大元素的位置。
将当前元素的下标入队到队列中，以便稍后可以根据下标获取元素。
遍历完成后，队列中剩余的元素表示没有找到下一个更大元素的位置，可以标记为-1或数组长度。
#include<bits/stdc++.h>
using namespace std;
long long n,h[1000005],v[1000005],ans[1000005];
void getmax() {
stack<long long>stk;//单调栈
for (long long i=1;i<=n;i++){//对于每一个i进行操作
while(!stk.empty()){
if(h[i]<=h[stk.top()]) break;//不符合要求
long long j=stk.top();
if(!stk.empty()){
ans[i]+=v[j];//h[j]<h[i] -> j向i发射
}
stk.pop();
}
if(!stk.empty()) ans[stk.top()]+=v[i];//没有别的高就是i向stk.top()发射
stk.push(i);
}
}
int main(){
cin>>n;
for(long long i=1;i<=n;i++){
cin>>h[i]>>v[i];
}
getmax();
long long maxx=-1;
for(long long i=1;i<=n;i++){
maxx=max(maxx,ans[i]);
}
cout<<maxx<<endl;
return 0;
}