本文主要是介绍算法【单调队列】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
注意，本文需要：
1.掌握用数组方式实现队列(常数时间比语言自己提供的好)。
2.掌握滑动窗口。
单调队列最经典的用法是解决如下问题：
滑动窗口在滑动时，r++代表右侧数字进窗口，l++代表左侧数字出窗口。这个过程中，想随时得到当前滑动窗口的最大值或者最小值。窗口滑动的过程中，单调队列所有调整的总代价为O(n)，单次操作的均摊代价为O(1)。
注意：这是单调队列最经典的用法，可以解决很多题目。后面将继续介绍其他的用法。
下面通过几个题目加深对经典用法的理解。
题目一
测试链接：https://leetcode.cn/problems/sliding-window-maximum/
分析：这道题就是一个单调队列的模板。代码如下。
class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> ans;int length = nums.size();int number = length - k + 1;ans.assign(number, 0);int left = 0;int right = k;int l = 0;int r = 0;int size = 0;int deque[100005] = {0};for(int i = left;i < right;++i){while (size > 0 && nums[i] >= nums[deque[r-1]]){--r;--size;}deque[r++] = i;++size;}for(int i = 0;i < number;++i){ans[i] = nums[deque[l]];if(i == number-1){break;}++left;if(deque[l] < left){++l;--size;}while (size > 0 && nums[right] >= nums[deque[r-1]]){--r;--size;}deque[r++] = right;++size;++right;}return ans;}
};其中，left和right是滑动窗口的左右，左开右闭；l和r是单调队列的头和尾，也是左开右闭；size为单调队列中元素个数；deque为单调队列。
题目二
测试链接：https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/
分析：这道题就是通过单调队列找到窗口的最大值和最小值，然后作差和limit去比较。遍历数组，从而得到最长连续子数组的长度。代码如下。
class Solution {
public:int longestSubarray(vector<int>& nums, int limit) {int length = nums.size();int ans = 0;int deque_max[100003] = {0};int deque_min[100003] = {0};int left = 0;int right = 0;int l_max = 0;int r_max = 0;int size_max = 0;int l_min = 0;int r_min = 0;int size_min = 0;for(;left < length && right < length;){while (nums[deque_max[l_max]] - nums[deque_min[l_min]] <= limit && right < length){while (size_max > 0 && nums[right] >= nums[deque_max[r_max-1]]){--r_max;--size_max;}deque_max[r_max++] = right;++size_max;while (size_min > 0 && nums[right] <= nums[deque_min[r_min-1]]){--r_min;--size_min;}deque_min[r_min++] = right;++size_min;++right;}if(nums[deque_max[l_max]] - nums[deque_min[l_min]] > limit){ans = ans > right - left - 1 ? ans : right - left - 1;}else{ans = ans > right - left ? ans : right - left;}if(right == length){break;}++left;if(deque_max[l_max] < left){++l_max;--size_max;}if(deque_min[l_min] < left){++l_min;--size_min;}}return ans;}
};其中，主要变量在上一题提及，这里不在赘述。窗口是以left为左边界向右能得到的最长满足条件的子数组。
题目三
测试链接：https://www.luogu.com.cn/problem/P2698
分析：这道题也是使用两个单调队列，得到窗口的最大值和最小值，和第二题类似。主要第三题采用了离散化，是因为给的点的数据不是连续的。代码如下。
#include <iostream>
#include <vector>
#include <algorithm>
#define MAXN 100002
using namespace std;
int N;
int D;
vector<vector<int>> pos;
int deque_max[MAXN] = {0};
int deque_min[MAXN] = {0};
int left = 0;
int right = 0;
int l_max = 0;
int r_max = 0;
int size_max = 0;
int l_min = 0;
int r_min = 0;
int size_min = 0;
class MyCompare
{
public:bool operator()(vector<int> v1, vector<int> v2){return v1[0] < v2[0];}
};
int main(void)
{int ans;int left = 0;int right = 0;scanf("%d%d", &N, &D);vector<int> temp;temp.assign(2, 0);pos.assign(N, temp);for (int i = 0; i < N; ++i){scanf("%d%d", &pos[i][0], &pos[i][1]);}sort(pos.begin(), pos.end(), MyCompare());ans = 1000005;for (; left < N && right < N;){while (pos[deque_max[l_max]][1] - pos[deque_min[l_min]][1] < D && right < N){while (size_max > 0 && pos[right][1] >= pos[deque_max[r_max - 1]][1]){--r_max;--size_max;}deque_max[r_max++] = right;++size_max;while (size_min > 0 && pos[right][1] <= pos[deque_min[r_min - 1]][1]){--r_min;--size_min;}deque_min[r_min++] = right;++size_min;++right;}if (pos[deque_max[l_max]][1] - pos[deque_min[l_min]][1] >= D){ans = ans < pos[right-1][0] - pos[left][0] ? ans : pos[right-1][0] - pos[left][0];}if (right == N){break;}++left;if (deque_max[l_max] < left){++l_max;--size_max;}if (deque_min[l_min] < left){++l_min;--size_min;}}printf("%d", ans == 1000005 ? -1 : ans);
}其中，先对点的位置按x的值进行了排序，代码基本思路和第二题一致。
除了单调队列最经典的用法之外，在很多问题里单调队列还可以维持求解答案的可能性。
1.单调队列里的所有对象按照规定好的单调性来组织。
2.当某个对象从队尾进入单调队列时，会从队头或者队尾依次淘汰单调队列里，对后续求解答案没有帮助的对象。
3.每个对象一旦从单调队列弹出，可以结算此时这个对象参与的答案，随后这个对象不再参与后续求解答案的过程。
4.其实是先有对题目的分析！进而发现单调性，然后利用单调队列的特征去实现。
题目四
测试链接：https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/
分析：看到此题，一个简单的思路是使用前缀和，利用双重for循环求解，不过从数据量可以看出这种思路会超时。所以不能单纯使用前缀和，要把前缀和和单调队列结合起来。首先得到前缀和数组，arr[i]表示前i和数的和，故arr[0] = 0 且arr的长度比nums的长度多1。单调队列的单调性是根据前缀和大压小，可以从两个方面考虑。一，根据求的前缀和数组中元素的单调顺序是从小到大。二，如果是小压大，假设单调队列中已经存在i，j，此时来了一个k，需要求以k为结尾满足条件的最长子数组，如果i和k满足条件，那么j和k也一定满足条件，因为arr[k]-arr[i] < arr[k]-arr[j]，并且因为i小于j，所以i没有存在的意义，则小压大不行。主题思路是，每来到一个元素，先从头开始判断是否满足条件，满足则更新答案然后将满足的元素从头弹出，直到不满足为止，接着按照大压小进队列。遍历数组即可得到答案。代码如下。
class Solution {
public:int shortestSubarray(vector<int>& nums, int k) {int length = nums.size();int ans = length + 1;long long arr[100005] = {0};int deque[100005] = {0};int head = 0;int tail = 0;arr[0] = 0;for(int i = 1;i <= length;++i){arr[i] = arr[i-1] + nums[i-1];}for(int i = 0;i <= length;++i){while (head < tail && arr[i] - arr[deque[head]] >= k){ans = ans < i - deque[head] ? ans : i - deque[head];++head;}while (head < tail && arr[i] <= arr[deque[tail-1]]){--tail;}deque[tail++] = i;}return ans == length+1 ? -1 : ans;}
};题目五
测试链接：https://leetcode.cn/problems/max-value-of-equation/
分析：将题中的yi + yj + |xi - xj|拆解开就是yi - xi + yj + xj，则对于来到的元素作结尾元素，想往前得到满足条件的最大值，由此可以看出单调队列的单调性是根据y-x的值小压大。则主体思路是，对于来到的元素，更新单调队列头部有可能过期的元素，然后和头元素计算值并更新答案，最后按照要求进队列。遍历数组即可得到答案。代码如下。
class Solution {
public:int findMaxValueOfEquation(vector<vector<int>>& points, int k) {int deque[100005] = {0};int ans = (1 << 31);int length = points.size();int head = 0;int tail = 0;for(int i = 0;i < length;++i){while (head < tail && points[i][0] - points[deque[head]][0] > k){++head;}if(head < tail){ans = ans > points[i][0] + points[i][1] + points[deque[head]][1] - points[deque[head]][0] ?ans : points[i][0] + points[i][1] + points[deque[head]][1] - points[deque[head]][0];}while (head < tail && points[i][1] - points[i][0] >= points[deque[tail-1]][1] - points[deque[tail-1]][0]){--tail;}deque[tail++] = i;}return ans;}
};其中，过期条件就是两个x间隔超过k，由题中条件推出。
题目六
测试链接：https://leetcode.cn/problems/maximum-number-of-tasks-you-can-assign/
分析：看到此题，在可以得出答案范围的情况下，考虑二分答案法（之前的文章有详细讲解），故主题思路通过二分答案法尝试答案，通过f方法判断。f方法返回是否能完成nums个任务，这里有一个贪心，我们只看能不能完成nums个任务，故可以用前nums个力量大的工人去完成前nums个力量小的任务，由此也可以看出，单调队列的单调性是根据所需力量值大压小。f方法的主体思路是，对于每一个来到的工人，先更新其不吃药时能够解锁的任务，然后判断队列中是否有任务，如果有则做头任务（所需力量最小），如果队列中没有任务，则在吃药的情况下，更新其能够解锁的任务，然后做尾任务（所需力量最大），这是因为不能让药浪费。代码如下。
class Solution {
public:bool f(vector<int>& tasks, vector<int>& workers, int pills, int strength, int tasks_length, int workers_length, int nums){int deque[50005] = {0};int head = 0;int tail = 0;int index = 0;int did = 0;if(did == nums){return true;}for(int i = workers_length-nums;i < workers_length;++i){while (index < tasks_length && tasks[index] <= workers[i]){deque[tail++] = index;++index;}if(head < tail && workers[i] >= tasks[deque[head]]){++did;if(did == nums){return true;}++head;}else{if(--pills == -1){return false;}while (index < tasks_length && tasks[index] <= workers[i] + strength){deque[tail++] = index;++index;}if(head < tail && workers[i] + strength >= tasks[deque[tail-1]]){++did;if(did == nums){return true;}--tail;}}}return false;}int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {int tasks_length = tasks.size();int workers_length = workers.size();sort(tasks.begin(), tasks.end());sort(workers.begin(), workers.end());int left = 0;int right = tasks_length < workers_length ? tasks_length : workers_length;int middle;int ans;while (left <= right){middle = (left + ((right - left) >> 1));if(f(tasks, workers, pills, strength, tasks_length, workers_length, middle)){left = middle + 1;ans = middle;}else{right = middle - 1;}}return ans;}
};其中，index是待解锁任务的起始下标；did是已经做了多少任务。
这篇关于算法【单调队列】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
