算法【单调队列】

注意，本文需要：

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是已经做了多少任务。