单调队列详解

大家好，又见面了，我是你们的朋友全栈君。

刚学单调队列时，在网上各大博客找文章学，说实话，写得很杂，表示自己懵逼了些许，最后硬是啃出来了，所以我决定要写一篇能让大部分人都看懂的博客来。

说单调队列，那我们就先说说这个单调队列是个什么物种。单调队列从字面上看，无非就是有某种单调性的队列，没错，这就是所谓的单调队列。 单调队列它分两种，一种是单调递增的，另外一种是单调递减的。

在这搬出百度百科的解释：不断地向缓存数组里读入元素，也不时地去掉最老的元素，不定期的询问当前缓存数组里的最小的元素。

用单调队列来解决问题，一般都是需要得到当前的某个范围内的最小值或最大值。

举个例子：有 7 6 8 12 9 10 3 七个数字，现在让你找出范围（ i-4，i ） 的最小值。

那我们就可以这样模拟一遍。

先初始化{ 0 } （表示i=0时的值）

i=1 ->{ 0 } （表示i=1,时，在其范围内最小的值为0）-> 7进队 { 7 } ；

i=2->{ 7 }（表示i=2,时，在其范围内最小的值为7）-> 6比7小，7出，6进 { 6 }；

i=3-> { 6 } （表示i=3,时，在其范围内最小的值为6）->8比6大，8进 { 6, 8}；

i=4->{ 6, 8}（表示i=4,时，在其范围内最小的值为6）-> 12比8大，12进 {6, 8 , 12};

i=5-> {6, 8 , 12}（表示i=4,时，在其范围内最小的值为6）-> 9比12小，12out，9比8大，9进 {6，8, 9}；

i=6-> {6，8, 9} 但是 单调队列中元素6的下标是2，不在（2, 6],中，故6 out，这就是单调队列的精髓了。故单调队列为

{ 8,9 }（表示i=5,时，在其范围内最小的值为8）->10比9大，10进 最终 单调队列为{ 8，9, 10} ;

i=7->{ 8，9, 10}（表示i=6,时，在其范围内最小的值为8）-> 3比单调队列为{ 8，9, 10} 的任意值都小，故全out，最终集合为 { 3 }；

相信大家看完这个例子了解得有些吧，再次重申一遍，单调队列的核心（我认为的哈）：得到当前的某个范围内的最小值或最大值。要不是这样的话，那还有必要这么麻烦找吗，直接找前面最小的就好了，可事实不是这样，题目是有限制的，规定在某个范围内找。

那我们就来看到例题，加深理解：

最大子序和

• Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
• Total Submission(s): 9 Accepted Submission(s): 2

Description

一个长度为n的整数序列，从中找出一段不超过m的连续子序列，使得整个序列的和最大。

例如： 1, -3, 5, 1, -2, 3

当m=4时，sum = 5+1-2+3 = 7

当m=2或m=3时，sum = 5+1 = 6

Input

多测试用例，每个测试用例：

第一行是两个正数n, m ( n, m ≤ 300000 )

第二行是n个整数

Output

每个测试用例输出一行：一个正整数，表示这n个数的最大子序和长度

Sample Input

6 4 1 -3 5 1 -2 3

Sample Output

7

这题可以用dp来解，在这我们就用单调队列来解。

我们先把序列的前i项和加起来并存到一个数组sum[ ]上，那么任意连续的子序列和就为sum [ i ] – sum[ j ] (i>j && j>i-m)。

那么我们就可以跟上述例子一样，一直更新就好了，每次找出在（i-m，i）范围内的最小sum[j]值。

代码一：

#include<cstdio> #include<algorithm>///单调队列， #include<cstring> #include<list> using namespace std; typedef long long LL; const int maxn=300010; LL sum[maxn]; list <int > que; int main() { int n,m; while(~scanf("%d%d",&n,&m)) { que.clear(); ///清除 sum[0]=0; for(int i=1;i<=n;i++) { scanf("%lld",&sum[i]); sum[i]=sum[i-1]+sum[i]; ///求前i项和 } ///初始化 LL maxs=sum[1]; que.push_front(1); for(int i=2;i<=n;i++) { while(!que.empty()&&i-que.back()>m) ///此步是判断是否在范围（i-m,i)内，不在就pop que.pop_back(); maxs=max(maxs,sum[i]-sum[que.back()]); ///求最大值，sum[i]-sum[min]，表示前i个中找到最小的来减，sum[min]就是单调队列的尾部sum[que.back()] while(!que.empty()&&sum[i]<sum[que.front()]) ///更新单调队列，比sum[i]大的值都去掉 que.pop_front(); que.push_front(i); ///最后将下标i入队 } printf("%lld\n",maxs); } return 8; } 

代码二：

#include<cstdio> ///单调递增序列（但保证最可能小） #include<algorithm> #include<cstring> using namespace std; typedef long long LL; const LL maxn=300010; LL sum[maxn]; LL index1[maxn]; ///存储下标 int main() { LL n,m; while(~scanf("%lld%lld",&n,&m)) { sum[0]=0; for(int i=1;i<=n;i++){ scanf("%lld",&sum[i]); sum[i]+=sum[i-1]; ///求前i项和 } ///初始化 int left=1,right=1; index1[1]=1; LL tmax=sum[1]; for(int i=2;i<=n;i++) { while(index1[left]<i-m) left++; ///不在范围（i-m，i）内，左移就好了 tmax=max(tmax,sum[i]-sum[index1[left]]); ///减去范围（i-m，i）内最小的值 while(right>=left&&sum[i]<sum[index1[right]]) ///排除比值sum[i]大的 right--; right++; index1[right]=i; ///将下标添加进去 } printf("%lld\n",tmax); } return 0; }

我的标签：做个有情怀的程序员！

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/152974.html原文链接：https://javaforall.cn