单调队列

定义

单调队列，即一种元素具有单调性的「双端」队列。

理解

单调队列中的元素从队首到队尾始终保持单调性（单调递增或单调递减），队首元素是所有队列元素中的一个最值（单调递增队列的队首元素是所有队列元素中的最小值，单调递减队列的队首元素是所有队列元素中的最大值）。

为了队列元素的单调性，单调队列的插入操作涉及两个步骤：

  1. 将一个元素插入单调栈队列之前，需要「在保证将该元素插入到队尾后整个队列满足单调性的前提下」队尾删除最少的元素。
  2. 待所有不满足单调性的元素都从队尾删除后，将当前元素插入队尾。

单调队列的删除操作，只需要直接从队首删除不符合要求的元素即可。

代码模板

单调递增队列

1
2
3
4
5
6
7
8
9
10
11
12
deque<int> dq; // 单调递增队列（从队首到队尾单调递增）
int num; // 待入队的元素

// 单调递增队列的插入操作
while(!dq.empty() && dq.back() >= num) dq.pop_back(); // 将不满足单调性的元素都从队尾删除
dq.push_back(num); // 将当前元素插入队尾

// 单调递增队列的删除操作
dq.pop_front(); // 从队首删除元素

// 单调递增队列中的最小值
int minn = dq.front();

单调递减队列

1
2
3
4
5
6
7
8
9
10
11
12
deque<int> dq; // 单调递减队列（从队首到队尾单调递减）
int num; // 待入队的元素

// 单调递减队列的插入操作
while(!dq.empty() && dq.back() <= num) dq.pop_back(); // 将不满足单调性的元素都从队尾删除
dq.push_back(num); // 将当前元素插入队尾

// 单调递减队列的删除操作
dq.pop_front(); // 从队首删除元素

// 单调递减队列中的最大值
int maxx = dq.front();

具体应用

滑动窗口的最大值

给定一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
每次只可以看到数组中在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
请计算每次滑动窗口中的最大值。

对于每个窗口 [i, i + k - 1]，需要求出这一窗口内的最大值。
定义一个单调队列，从队首到队尾单调递减。
对于数组的前 k 个元素，依次执行单调队列的插入操作，则执行完成后队首的元素即为第一个窗口中的最大值。
此后开始移动窗口，每次窗口的区间范围从 [i - 1, i + k - 2] 变为 [i, i + k - 1]，则区间内参与评选最大值的数，需要删除 nums[i - 1] 并且增加 nums[i + k - 1]。
增加 nums[i + k - 1]，即执行一次单调队列的插入操作即可。
至于删除 nums[i - 1] 的操作，如果在执行完增加 nums[i + k - 1] 的操作后，位于队首的元素是 nums[i - 1]，即此时的最大值由 nums[i - 1] 贡献，但 nums[i - 1] 不应该出现在当前窗口内，则需要执行单调队列的删除操作（删除队首元素），让原队列中的第二个元素替补作为最大值。如果队首元素不是 nums[i - 1]，即此时的最大值由 nums[i] 到 nums[i + k - 1] 中的其他值贡献，则不需要做删除操作。
执行完以上两步操作，则单调队列的队首元素就是当前窗口内的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
vector<int> nums; // 整数数组 nums
int n; // 整数数组 nums 的长度
deque<int> dq; // 单调队列（队列中记录元素的下标）
vector<int> res; // 结果数组，res[i] 存储窗口 [i, i + k - 1] 内的最大值

// 数组的前 k 个元素，依次执行单调队列的插入操作
for(int i = 0; i < k; i++){
    while(!dq.empty() && nums[dq.back()] <= nums[i]){
        dq.pop_back();
    }
    dq.push_back(i);
}

// 队首的元素即为第一个窗口中的最大值
res.push_back(nums[dq.front()]);

for(int i = 1; i < n - k + 1; i++){
    // 在单调队列中增加 nums[i + k - 1]，即新窗口的右端点
    while(!dq.empty() && nums[dq.back()] <= nums[i + k - 1]){
        dq.pop_back();
    }
    dq.push_back(i + k - 1);

    // 在单调队列中删除 nums[i - 1]，即上一个窗口的左端点
    while(!dq.empty() && dq.front() <= i - 1)  dq.pop_front(); // 元素下标小于等于 i - 1，则从队首删除
    
    res.push_back(nums[dq.front()]); // 此时队首元素即为当前窗口中的最大值
}

最大子序和

给定一个整数数组 nums（可能包含负数），从中找出一段长度不超过 M 的连续子数组，使得子数组中所有数的和最大。

计算“区间和”的问题，一般转化为“前缀和相减”的问题进行求解。
设 S[i] 表示数组前 i 项的前缀和，则原问题可以转化为：找到一个区间 [x, y]（x < y），使得 S[y] - S[x] 最大并且 y - x <= M。
首先枚举右端点 y，当 y 固定时，问题转化为：找到一个左端点 x，其中 x 在区间 [y - M, y - 1] 范围内，并且 S[x] 最小。
比较区间 [y - M, y - 1] 内的任意两个位置 x 和 x’，如果 x’ < x 并且 S[x’] < S[x]，那么对于所有大于等于 y 的右端点， x’ 永远不会称为最优选择。因为不但 S[x’] 不小于 S[x]，而且 x 距离 y 更近，子数组的长度更不容易超过 M，即 x 的优先程度比 x’ 更高。所以如果有了 x，则 x’ 就变成一个完全无用的位置。
因此，有可能成为最优选择的元素集合一定是一个「下标位置递增、对应前缀和 S 的值也递增」的序列，这符合单调队列的特征。

定义一个单调队列，从队首到队尾单调递增，保存最优选择的元素集合。
遍历前缀和数组的所有位置，对每个位置 y 执行如下操作：

  1. 判断队首元素与 y 的距离是否超过 M，如果超出则队首元素出队，依次出队直到队首元素与 y 的距离不超过 M。
  2. 此时队首元素就是右端点为 y 时，最优的左端点位置（与 y 的距离不超过 M 并且对应前缀和 S 最小）。
  3. 执行单调队列的插入操作，将当前位置 y 的前缀和 S[y] 插入单调队列，作为后续位置的一个左端点选择项。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int M;
int n; // 整数数组 nums 中的元素个数
vector<int> nums(n + 1); // nums[1] 到 nums[n] 存储 n 个整数
vector<int> sum(n + 1); // 对应数组 nums 的前缀和数组

// 计算前缀和
sum[0] = 0;
for(int i = 1; i <= n; i++){
    sum[i] = sum[i - 1] + nums[i];
}

int ans = INT_MIN; // 初始化答案变量
deque<int> dq; // 单调队列（队列中记录元素的下标）

dq.push_back(0);
for(int i = 1; i <= n; i++){
    while(!dq.empty() && dq.front() < i - M) dq.pop_front(); // 与当前右端点距离超过 M 的队首元素全部出队
    ans = max(ans, sum[i] - sum[dq.front()]); // 此时队首元素即为对应当前右端点的最优左端点
    // 在单调队列中增加 sum[i]
    while(!dq.empty() && sum[dq.back()] >= sum[i])  dq.pop_back();
    dq.push_back(i);
}
cout << ans << endl;