单调队列-下

---

基本介绍

除了单调队列最经典的用法之外，在很多问题里单调队列还可以维持求解答案的可能性

（1）单调队列里的所有对象按照规定好的单调性来组织

（2）当某个对象从队尾进入单调队列时，会从队头或队尾依次淘汰单调队列里对后续求解答案没有帮助的对象

（3）每个对象一旦从单调队列弹出，可以结算此时这个对象参与的答案，随后这个对象不再参与后续求解答案的过程

（4）其实是先有对题目的分析！进而发现单调性，然后利用单调队列的特征去实现

⚠️ 注意

单调队列可以和很多技巧交叉使用！比如：动态规划 + 单调队列优化，会在【扩展】课程里讲述

和至少为 K 的最短子数组

题目链接

https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k

思路分析

单调队列队头队尾指针 [ h，t ）左闭右开

子数组的和，可以使用前缀和技巧，来到 i 位置，希望向左延申尽量短且该子数组的和 >= k

子树组的和 = i 位置的前缀和 - 尽量靠右的位置 j 的前缀和，且结果能满足 >= k

前缀和具有单调性，使用单调队列存储元素下标，队列中从左到右是从小到大的结构

队头维护较小的前缀和，如果队头符合，则弹出，靠后的元素如果满足差值前缀和 >= k 的情况下，子数组才会尽可能的短，更新子数组的长度

若 i 位置的前缀和比队尾元素的前缀和小，说明是出现了负数导致的，i 位置需要入队，但是此时破坏了队列的单调性，队尾不断弹出元素，直到不破坏队列中的单调性为止

代码实现

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int MAXN = 100001;
        // sum[0] : 前0个数的前缀和
        // sum[i] : 前i个数的前缀和
        long[] sum = new long[MAXN];
        int[] deque = new int[MAXN];
        int h = 0, t = 0;
        for (int i = 0; i < nums.length; i++) {
            // 数组 [3,4,5]
            // 索引  0 1 2
            // sum[0] = 0，sum[1] = 3，sum[2] = 7
            // sum[i] 表示前 i 个数的前缀和
            sum[i + 1] = sum[i] + nums[i];
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i <= nums.length; i++) {
            while (h != t && sum[i] - sum[deque[h]] >= k) {
                ans = Math.min(ans, i - deque[h]);
                h++;
            }
            // 前 i 个数的前缀和从队尾进入
            while (h != t && sum[deque[t - 1]] >= sum[i]) {
                t--;
            }
            deque[t++] = i;
        }
        return ans != Integer.MAX_VALUE ? ans : -1;
    }
}

满足不等式的最大值

题目链接

https://leetcode.cn/problems/max-value-of-equation/

思路分析

题目中的指明了 i < j，式子转为 后 y + 前 y + 后 x - 前 x，进一步转化为如下形式

后 x + 后 y + 前 y - 前 x，只需要使 前 y - 前 x 尽可能的大即可，同时还要满足后 x - 前 x <= k

单调队列队头队尾指针 [ h，t ）左闭右开，存储 i 号点对应的下标，队头到队尾维护 前 y - 前 x 从大到小的单调性

代码实现

class Solution {
    public int findMaxValueOfEquation(int[][] points, int k) {
        int MAXN = 100001;
        // [...i号点[x,y]...]
        int[][] deque = new int[MAXN][2];
        int h = 0, t = 0;
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < points.length; i++) {
            // 后面点的 x，y
            int x = points[i][0];
            int y = points[i][1];

            // 后面点的 x - 前面点的 x <= k
            while (h < t && x - deque[h][0] > k) {
                h++;
            }
            if (h < t) {
                // 题中指明 i < j，式子转为 --> 后 y + 前 y + 后 x - 前 x
                // 进一步转化为 --> 后 x + 后 y + 前 y - 前 x
                ans = Math.max(ans, x + y + deque[h][1] - deque[h][0]);
            }
            // i 号点的 x，y 进入单调队列，维护 前 y - 前 x 从大到小的单调性
            while (h < t && deque[t - 1][1] - deque[t - 1][0] <= y - x) {
                t--;
            }
            deque[t][0] = x;
            deque[t][1] = y;
            t++;
        }
        return ans;
    }
}

你可以安排的最多任务数目

题目链接

https://leetcode.cn/problems/maximum-number-of-tasks-you-can-assign/

思路分析

本题思路：二分答案 + 贪心 + 单调队列

二分答案：工人完成的任务数量是有范围的，最小为 0，最大为任务数和工人数量取最小值

贪心思想：需要完成任务，优先选力量大的工人去完成需要力量小的任务，所以对两个数组排序

单调队列：单调性由数组排序实现，利用了队列的特点，队列中存储任务编号，f 函数设计如下

（1）不吃药的情况下，看该工人的能力可以解锁多少任务，将任务从队尾放入

（2）不吃药的情况下，工人能完成对应的任务，任务从队头弹出

（3）如果能力无法完成某个任务，则吃药，吃药后能解锁任务，将任务从队尾放入

（4）吃药后能完成某个任务，根据贪心思想应优先完成需要能力较大的任务，任务从队尾弹出

（5）如果无法完成任务，或者药丸的使用超出限制，返回 false，表示此时的任务数无法完成

代码实现

class Solution {
    int MAXN = 50001;

    int[] deque = new int[MAXN];

    public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
        Arrays.sort(tasks);
        Arrays.sort(workers);
        int tSize = tasks.length;
        int wSize = workers.length;
        int ans = 0;

        // 二分答案
        int l = 0;
        int r = Math.min(tSize, wSize);
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            // 判定 mid 个任务数能否完成
            // wSize - mid 表示从最后一工人开始往前数 mid 个
            if (f(tasks, workers, 0, mid - 1, wSize - mid, wSize - 1, strength, pills)) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }

    // tasks 的 tl，tr 表示任务中需要能力较小的几个任务
    // workers 的 wl，wr 表示能力较大的几个工人
    // 返回在这些条件的情况下能否完成 mid 个任务
    public boolean f(int[] tasks, int[] workers, int tl, int tr, int wl, int wr, int s, int pills) {
        // 队头与队尾指针
        int h = 0, t = 0;

        // 已经使用的药丸数量
        int cnt = 0;

        // i ：工人的编号，j ：任务的编号
        for (int i = wl, j = tl; i <= wr; i++) {
            // 工人不吃药的情况下，将解锁的任务放到队列中
            for (; j <= tr && tasks[j] <= workers[i]; j++) {
                deque[t++] = j;
            }
            // 工人完成任务，将任务从队头弹出
            if (h < t && tasks[deque[h]] <= workers[i]) {
                h++;
            } else {
                // 吃药后如果能解锁任务，将任务从队尾放入
                for (; j <= tr && tasks[j] <= workers[i] + s; j++) {
                    deque[t++] = j;
                }
                // 如果队列里有任务
                if (h < t) {
                    // 吃了一颗药丸
                    cnt++;
                    // 排序后，加入队列中的任务一定是从小到大的
                    // 吃药后优先选择队尾的任务，任务从队尾弹出
                    t--;
                } else {
                    // 当前员工吃药之后都无法解锁任务
                    // 则 mid 个任务无法完成，返回 false
                    return false;
                }
            }
        }
        // 任务都可以完成的情况下，使用的药丸数量不能超过题目限制
        return cnt <= pills;
    }
}