单调队列详解

秒速五厘米 2022-10-29 07:39 165阅读 0赞

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

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

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

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

**举个例子：有  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

这题可以用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;
    }