大家好，又见面了，我是你们的朋友全栈君。
前言 嘿！彩蛋！感觉有帮助就三连呗！
如果你对这篇文章可感兴趣，可以点击「【访客必读 – 指引页】一文囊括主页内所有高质量博客」，查看完整博客分类与对应链接。
在上一篇文章中，我们介绍了「单调栈」这一最常考察的线性数据结构。而今天我们将继续沿着这个思路，介绍另一个与其 “齐名” 的线性数据结构，即「单调队列」。
「单调队列」在「数据结构」题中的分布较为广泛，且常被当作优化「动态规划」的一种重要手段，因此该算法在面试中考察的频率较高，属于必知必会的知识点。
队列
首先我们来回忆一下「队列」。「队列」是一种「先进先出」的线性数据结构，其中元素只能从队尾进，从队首出。
如下图所示，3 1 4 5 2 7 依次入队又依次出队，其结果满足「先进先出」的要求。另外，有标记的位置分别代表队首与队尾，其中左边为队首。
单调队列
回忆完「队列」后，我们开始「单调队列」的讲解。
什么是「单调队列」？顾名思义，「单调队列」就是队列内元素满足单调性的队列结构。且为了满足队列内元素的单调性，队尾也可弹出元素。此处的单调性分为单调递增与单调递减，为了便于描述，接下来以「单调递增队列」为例进行讲解。
「单调递增队列」中「队尾」的操作与「单调递增栈」中「栈顶」的操作一致，即假设当前元素为 x，若队尾元素 <= x，则将 x 入队，否则不断弹出队尾元素，直至队尾元素 <= x。
例如以 3 1 4 5 2 7 为例，若「队首」始终不弹出元素，则其具体过程如下图所示。
由此可知，「单调队列」与「单调栈」的最大区别就在于「队首」的操作，「何时将队首元素出队」是「单调队列」算法的关键。
然而「队首」的操作往往具有多样性，并非一成不变，因此接下来我们以三道经典题型为例来进一步讲解该算法。
习题讲解
239. 滑动窗口最大值
题目描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例 1
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2
输入：nums = [1], k = 1
输出：[1]
示例 3
输入：nums = [1,-1], k = 1
输出：[1,-1]
示例 4
输入：nums = [9,11], k = 2
输出：[11]
示例 5
输入：nums = [4,-2], k = 2
输出：[4]
提示
1 <= nums.length <= 1e5-1e4 <= nums[i] <= 1e41 <= k <= nums.length
题目讲解
「滑动窗口中的最大 / 小值」是「单调队列」最为经典的应用，其它「单调队列」的题型大多从该模型演变而来，因此大家需要着重理解此题。
由于本题求的是「滑动窗口中的最大值」，因此我们使用「单调递减队列来进行解决」。另外由于窗口大小为 k，所以当窗口右端点下标为 r 时，影响当前窗口最大值的元素下标范围为 [r-k+1, r]。
由此我们可以制定「队首」弹出元素的规则，即当「队尾元素的下标 – 队首元素的下标 + 1」大于 k 时，弹出「队首」元素。
接下来我们以 nums = [3 2 1 -1 2]、k = 3 为例，展示「单调递减队列」的具体执行过程。且为了便于展示，我们在「单调队列」中存储的是元素的下标，而不是元素的数值。
观察上述执行过程，我们可以发现元素入队分为两步，第一步是「不断弹出队尾元素」直至队尾元素代表的数值大于等于当前元素，第二步是「弹出队首元素」直至「当前元素下标 – 队首元素下标 + 1」小于等于 k。
进一步观察可以发现，当前元素入队的两步操作结束后，以当前元素为右端点的窗口，其窗口最大值为「队首元素」所对应的数值。
我们以当前元素为第四个元素（即 -1）为例来帮助大家理解。
此时队尾数值为 nums[3] = 1，即队尾数值大于等于当前元素，因此当前元素入队（队列中存储元素下标），如下图所示。
入队后「弹出队首元素」直至「当前元素下标 – 队首元素下标 + 1」小于等于 k，因此队首元素被弹出，最终状态如下图所示。
第四个元素完成上述两步入队操作后，队首元素下标为 2，其对应的数值 nums[2] = 2，当前窗口最大值 max([2 1 -1]) = 2。因此印证了刚才的结论，即当前元素入队的两步操作结束后，以当前元素为右端点的窗口，其窗口最大值为「队首元素」所对应的数值。
由此我们可以发现「单调队列」的核心功能为「求出数组中每一个元素其固定区间范围内的最大 / 小值」。并且由于每个元素出队、入队最多一次，因此总的时间复杂度为 O(n)。
根据上述算法即可解决本题，具体实现细节见下述代码。
代码实现
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int len = nums.size(), l = 0, r = -1;
vector<int> q(len, 0), ans;
for (int i = 0; i < len; i++) {
while (l <= r && nums[q[r]] < nums[i]) r--;
q[++r] = i;
if (i-q[l]+1 > k) l++;
if (i >= k-1) ans.push_back(nums[q[l]]);
}
return ans;
}
};
1425. 带限制的子序列和
题目描述
给你一个整数数组 nums 和一个整数 k ，请你返回「非空」子序列元素和的最大值，子序列需要满足：子序列中每两个「相邻」的整数 nums[i] 和 nums[j]，它们在原数组中的下标 i 和 j 满足 i < j 且 j – i <= k 。
数组的子序列定义为：将数组中的若干个数字删除（可以删除 0 个数字），剩下的数字按照原本的顺序排布。
示例 1
输入：nums = [10,2,-10,5,20], k = 2
输出：37
解释：子序列为 [10, 2, 5, 20] 。
示例 2
输入：nums = [-1,-2,-3], k = 1
输出：-1
解释：子序列必须是非空的，所以我们选择最大的数字。
示例 3
输入：nums = [10,-2,-10,-5,20], k = 2
输出：23
解释：子序列为 [10, -2, -5, 20] 。
提示
1 <= k <= nums.length <= 1e5-1e4 <= nums[i] <= 1e4
题目讲解
本题求解的是最大「非空」子序列元素和，且相邻两个元素坐标差小于等于 k。由于题目的主体是子序列，因此我们采取一种「增量式」的思想来进一步思考。
假设当前有一个子序列 A，现在想在 A 后面再添加一个元素 x，则我们只需要考虑 x 和 A 中最后一个元素的坐标差是否小于等于 k，而不用考虑 A 中的所有元素。更明确地说，对于子序列 A，我们只需要记录它的元素和与最后一个元素的下标即可。
基于上述的思考，不难想到使用动态规划的算法，令 f[i] 表示以 nums[i] 为子序列最后一个元素时的最大元素和，则可以得到如下递推公式：
f [ i ] = max ( f [ j ] , 0 ) + n u m s [ i ] ( i − k ≤ j < i ) f[i]=\max(f[j],0)+nums[i]\ \ \ (i-k\leq j<i) f[i]=max(f[j],0)+nums[i] (i−k≤j<i)
根据上述公式，我们可以得到一种暴力的做法，即对于每一个 i，向前枚举合法的 j 来更新 f[i]，时间复杂度为 O(nk)。
观察题目中的数据范围，暴力做法很明显无法通过，因此我们考虑如何优化。
f[i] 由前面 k 个数中的最大值转移而来，因此不难想到使用「单调队列」算法来进行优化。用「单调队列」来维护 f 数组中大小为 k 的窗口的最大值即可完成此题，时间复杂度优化至 O(n)，具体细节见代码。
通过此题，我们可以更深刻地意识到，「单调队列」在求取「数组中每一个元素其固定区间范围内的最大 / 小值」的作用。而也正是该功能，使得「单调队列」常作为「动态规划」的一种优化手段出现在面试题中。
代码实现
class Solution {
public:
int constrainedSubsetSum(vector<int>& nums, int k) {
int len = nums.size(), l = 0, r = -1, ans = nums[0];
vector<int> q(len, 0);
for (int i = 0; i < len; i++) {
if (l <= r && i - q[l] > k) l++;
if (l <= r) nums[i] = max(nums[i], nums[i] + nums[q[l]]);
ans = max(ans, nums[i]);
while (l <= r && nums[q[r]] < nums[i]) r--;
q[++r] = i;
}
return ans;
}
};
862. 和至少为 K 的最短子数组
题目描述
返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。
如果没有和至少为 K 的非空子数组，返回 -1。
示例 1
输入：A = [1], K = 1
输出：1
示例 2
输入：A = [1,2], K = 4
输出：-1
示例 3
输入：A = [2,-1,2], K = 3
输出：3
提示
1 <= A.length <= 50000-1e5 <= A[i] <= 1e51 <= K <= 1e9
题目讲解
本题求解的是元素和大于等于 K 的最短非空连续子数组，由于涉及连续子数组和的求取，所以先对 A 做一个前缀和。
令 B 为 A 的前缀和数组，即 A 在 [x, y] 区间的元素和等于 B[y] – B[x-1]。又因为我们需要求解元素和大于等于 K 的最短连续子数组，即对于 B[y] 来说，找到最大的 x 满足 0 <= x < y 且 B[y] – B[x] >= K，也就是说，我们既希望 B[x] 小又希望 x 大。
基于上述观察，我们可以维护一个单调递增队列 [x1, x2, …, xp] 存储所有可能更新答案的下标 x（左边为队首）。队列满足从左至右，下标递增且下标对应的 B 中元素值也递增。
假设当前元素为 B[y]，若 B[xp] > B[y] 则弹出，因为 y 比 xp 更大且 B[y] 比 B[xp] 更小，即 y 一定比 xp 更优。基于该策略不断弹出队尾元素，直至条件不再满足。
对于队首元素来说，若 B[y] – B[x1] >= K，则弹出 x1 并更新答案 ans = min(ans, y – x1)。因为 y 是不断变大的，就算之后存在 y’ > y 满足 B[y’] – B[x1] >= K，y 距 x1 仍近于 y’，因此可以直接将 x1 弹出而不影响答案。基于该策略不断弹出队首元素，直至条件不再满足。
另外，上述算法未考虑到区间 [1, y] 的情况，因此若 B[y] >= K，则更新答案 ans = min(ans, y)。
观察上述算法，可以发现队尾操作与基础题「滑动窗口」没有区别，主要变化在于「队首弹出元素」的条件，而本题也正是通过对该条件的修改使得题目思维难度变大。
代码实现
class Solution {
public:
int shortestSubarray(vector<int>& A, int K) {
int len = A.size(), l = 0, r = -1, ans = len+1;
vector<int> q(len, 0);
for (int i = 1; i < len; i++) A[i] += A[i-1];
for (int i = 0; i < len; i++) {
while (l <= r && A[q[r]] > A[i]) r--;
q[++r] = i;
while (A[q[r]]-A[q[l]] >= K) {
ans = min(ans, q[r]-q[l]);
l++;
}
if (A[i] >= K) ans = min(ans, i+1);
}
if (ans == len+1) ans = -1;
return ans;
}
};
总结
通过上述三道例题的讲解，希望大家对于「单调队列」有了更多的了解，其实「单调队列」就是在「单调栈」的基础上加了一个「弹出队首」的操作，虽然该操作的添加极大地增加了该算法的多样性。
不过作为初学者，大家只需要理解「单调队列」在「滑动窗口」问题上的应用即可，即在 O(n) 时间复杂度内求出数组中每一个元素其固定区间范围的最大 / 小值。
至此我们完成了两大基础线性数据结构的讲解（单调栈与单调队列），这两个数据结构的变化较多，大家需要在日后刷题的过程中进一步地感受与体会，祝大家日益精进，刷题愉快！
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/152970.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...
