队列学习笔记"/>
单调队列学习笔记
简介
单调队列是一种特殊的双端队列（但是不要用 deque 存储），其内部元素具有单调性。
单调队列有如下操作：
- 插入：新元素从队尾插入会破坏单调性，所以删除队尾元素，直到找到插入后不会破坏单调性的位置，再将元素插入。
- 获取最大（最小）值：访问队首元素。
单调队列优化 DP 时，每个元素通常存储两个值：
- 在原数列的位置，即下标
- 在 DP 中的状态值
由于每个元素最多出队一次，进队一次，所以时间复杂度为 O ( n ) O(n) O(n)。
应用
定长连续子区间问题
滑动窗口
朴素算法
直接扫描，枚举起始元素 a x a_x ax，然后求区间 ( a x , a x + k − 1 ) (a_x,a_x+k-1) (ax,ax+k−1) 的最大值和最小值。
时间复杂度为 O ( n k ) O(nk) O(nk)。
线段树或RMQ
时间复杂度为 O ( n log n ) O(n\log n) O(nlogn)。
单调队列
对于相邻两个区间 ( l , r ) (l,r) (l,r) 和 ( l + 1 , r + 1 ) (l+1,r+1) (l+1,r+1)，有如下性质：
序列： a l , a l + 1 , a l + 2 , ⋯ , a r − l , a r , a r + 1 a_l,a_{l+1},a_{l+2},\cdots,a_{r-l},a_r,a_{r+1} al,al+1,al+2,⋯,ar−l,ar,ar+1。
max ( a l , a l + 1 , a l + 2 , ⋯ , a r − l , a r ) = max ( a l , max ( a l + 1 , a l + 2 , ⋯ , a r − l , a r ) ) \max(a_l,a_{l+1},a_{l+2},\cdots,a_{r-l},a_r)=\max(a_l,\max(a_{l+1},a_{l+2},\cdots,a_{r-l},a_r)) max(al,al+1,al+2,⋯,ar−l,ar)=max(al,max(al+1,al+2,⋯,ar−l,ar))
max ( a l + 1 , a l + 2 , ⋯ , a r − l , a r , a r + 1 ) = max ( max ( a l + 1 , a l + 2 , ⋯ , a r − l , a r ) , a r + 1 ) \max(a_{l+1},a_{l+2},\cdots,a_{r-l},a_r,a_{r+1})=\max(\max(a_{l+1},a_{l+2},\cdots,a_{r-l},a_r),a_{r+1}) max(al+1,al+2,⋯,ar−l,ar,ar+1)=max(max(al+1,al+2,⋯,ar−l,ar),ar+1)
两个方程有相同的部分，于是乎，在求 ( l + 1 , r + 1 ) (l+1,r+1) (l+1,r+1) 的最值的时候，无需在扫描一次，只有当上一次的最值在 a l a_l al 上时才需要重新扫描。
除此之外，对任意的 l ≤ i ≤ j ≤ r l\leq i\leq j\leq r l≤i≤j≤r，如果 a i < a j a_i<a_j ai<aj，那么在区间向右移动时，最大值一定不会落在 a i a_i ai 上。
当将区间从 ( l , r ) (l,r) (l,r) 移动到 ( l + 1 , r + 1 ) (l+1,r+1) (l+1,r+1) 时，若队首元素不在 ( l + 1 , r + 1 ) (l+1,r+1) (l+1,r+1) 中，删除队首，将 a r + 1 a_{r+1} ar+1 插入到单调队列中合适的位置。
时间复杂度为 O ( n ) O(n) O(n)。
#include <bits/stdc++.h>
using namespace std;
#define int long longconst int maxn=1e6+5;
int q1[maxn],q2[maxn],a[maxn];signed main()
{int n,k;cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i];int h1=1,t1=0,h2=1,t2=0;for(int i=1;i<=n;i++){while(h1<=t1&&q1[h1]+k<=i) h1++;while(h1<=t1&&a[q1[t1]]>a[i]) t1--;q1[++t1]=i;if(i>=k) cout<<a[q1[h1]]<<' ';}cout<<endl;for(int i=1;i<=n;i++){while(h2<=t2&&q2[h2]+k<=i) h2++;while(h2<=t2&&a[q2[t2]]<a[i]) t2--;q2[++t2]=i;if(i>=k) cout<<a[q2[h2]]<<' ';}return 0;
}
更多推荐
单调队列学习笔记
发布评论