单调队列 | 野生开发者

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

一篇详细的博客：传送门

例如：

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来解，也可以用单调队列。

方法一：(第一反应的做法，当然没有完全按照题目的输出，主要是用于检验)

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int a[300005];

int main(){
    int n, m;
    while(cin >> n >> m){
        memset(a, 0, sizeof(a));
        for(int i = 0; i < n; i++)
            cin >> a[i];
        int ans = 0, t = 0, temp = 0, len = 0, ans_l = 0, ans_t = 0;
        while(t + len < n){
            for(int i = t; i < t + m; i++){
                temp += a[i];
                len++;
                if(ans < temp){
                    ans = temp;
                    ans_l = len;
                    ans_t = t;
                }
            }
            t++;
            len = 0; temp = 0;
        }
        cout << "start: " << ans_t << " " << "length: " << ans_l << endl;
        cout << ans << endl;
    }
    return 0;
}

方法二：(单调队列)

//跟前缀和差不多
#include <iostream>
#include <algorithm>
#include <cstring>
#include <list>
using namespace std;

#define MIN -0x7fffffff
int sum[300005];
list <int> L;

int main(){
    int n, m;
    while(cin >> n >> m){
        memset(sum, 0, sizeof(sum));
        sum[0] = 0;  //注意：这里一定要从sum[1]开始存储，并且设置sum[0] = 0，原因可以从下面的for循环和两个while循环推出
        cin >> sum[1];
        for(int i = 2; i <= n; i++){
            cin >> sum[i];
            sum[i] += sum[i - 1];
        }
        L.clear();
        int ans = MIN;
        L.push_front(0);  //将下标i入队
        for(int i = 1; i <= n; i++){
            while(!L.empty() && i - L.back() > m){  //判断是否在范围（i-m,i)内，不在就pop
                L.pop_back();
            }
            ans = max(ans, sum[i] - sum[L.back()]);  //求最大值，sum[i]-sum[min]，表示前i个中找到最小的来减，sum[min]就是单调队列的尾部sum[L.back()]
            while(!L.empty() && sum[i] < sum[L.front()]){  //更新单调队列，比sum[i]大的值都去掉
                L.pop_front();
            }
            L.push_front(i);  //最后将下标i入队
        }
        cout << ans << endl;
    }
    return 0;
}

/*
Input:
9 5
3 7 -2 9 -9 6 5 -4 7
6 4
1 -3 5 1 -2 3
Output:
17
7
*/