单调队列-下

题目1

题目链接：862. 和至少为 K 的最短子数组

解题思路

1. 前缀和加单调双端队列，维护一个单增的单调序列，存放前缀和数组的下标，对于数组中的每个位置i，我们要找到以它为结尾的和至少为k的最短子数组，要在前面找到一个最右边界，使得sum[i] - sum[x] >= k,i-x即为以i结尾的最短长度，只需比较数组每个元素作为最后一个元素的最小值即可找到答案
2. 删除队首：当 sum[i] - sum[deque[h]] >= k 时，说明找到了一个满足条件的子数组，记录长度并弹出队首（因为后续更大的 i 不会得到更短的结果）
3. 删除队尾：如果当前 sum[i] <= sum[deque[t-1]]，那么 deque[t-1] 这个位置永远不会再被用作左端点，因为 i 更靠右且前缀和更小，是更好的选择

代码

class Solution {
    public static int MAXN = 100001;
    public static long[] sum = new long[MAXN];//sum[i]表示前i个数的前缀和
    public static int[] deque = new int[MAXN];
    public static int h,t;
    public int shortestSubarray(int[] nums, int k) {
        h=t=0;
        int n = nums.length;
        int ans = Integer.MAX_VALUE;
        for(int i = 0;i < n;i++){
            sum[i+1] = sum[i] + nums[i];
        }
        for(int i = 0;i <= n;i++){
            while(h < t && sum[i] - sum[deque[h]] >= k){
                   ans = Math.min(ans,i-deque[h++]);
            }
            while(h < t && sum[i] <= sum[deque[t-1]]){
                t--;
            }
         
            deque[t++] = i;
        }
        return ans != Integer.MAX_VALUE ? ans : -1;
    }
}

题目2

题目链接：1499. 满足不等式的最大值

解题思路

1. yi + yj + |xi - xj|等价于(xj+yj)+(yi-xi),即在规定范围内（(xj-xi)<=k）找(yi-xi)的最大值
2. 我们维护一个****双端队列，队列中存储的是候选点 (xi, yi)，并按照 (yi - xi) 从大到小排列（即队首是当前窗口内 (yi - xi) 最大的点）
3. 移除过远的点，若队首满足xj-xi>k，说明它不再合法窗口内，从队首弹出
4. 更新答案，如果队列非空，队首就是答案
5. 维护队列单调性，把当前点（xj,yj）加到队列前，从队尾删除所有(yi-xi)<=(yj-xj)的点
   • **当前点更靠右（x 更大），未来能存活更久（不容易被 **xj - xi > k 踢出）
   • **且 **(yj - xj) 更大，是更优的候选

代码

class Solution {
    public static int MAXN = 100001;
    public static int[][] deque = new int[MAXN][2];
    public static int h,t;
    public int findMaxValueOfEquation(int[][] points, int k) {
        h=t=0;
        int ans = Integer.MIN_VALUE;
        int n = points.length;
        for(int i = 0;i < n;i++){
            int x = points[i][0];
            int y = points[i][1];
            //不满足题意，即距离过长
            while(h < t&& (x - deque[h][0]) > k){
                h++;
            }//记录答案
            if(h < t){
                ans = Math.max(ans,x+y+deque[h][1]-deque[h][0]);
            }
            //(y-x)更大，更满足要求
            while(h < t&& (y-x) >= (deque[t-1][1] - deque[t-1][0])){
                t--;
            }
            deque[t][0] = x;
            deque[t++][1] = y;
        }
        return ans;
    }
}

题目3

题目链接：2071. 你可以安排的最多任务数目

解题思路（二分+贪心+双端队列）

1. 解决任务的范围是0,Math.min(tsize,wsize),右侧为任务数和工人数的最小值，如果能完成一半的任务，记录答案，去右侧二分，否则去左侧二分，现在的难点是能否完成这么多的任务
2. 我们将任务数组和工人数组排好序
   • 我们可以在 tasks 中选择 k 个值最小的任务；
   • 我们可以在 workers 中选择 k 个值最大的工人。
   • 遍历工人数组，如果工人不吃药就能解决任务，把能解决的任务加入队列，并弹出队首（该任务被解决）
   • 如果工人不吃药解决不了任务，吃药，并将吃药后能解决的任务加到队列，并弹出队尾(发挥药的最大作用)，如果吃药仍不能解决任务，直接返回false,用cnt变量记录所用药数,如果所需药数小于等于所给药数，返回true

代码

class Solution {
    public static int MAXN = 50001;
    public static int[] deque = new int[MAXN];
    public static int h,t;
    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;
        for(int l = 0,r = Math.min(tsize,wsize);l <= r;){
            int m = l + (r-l)/2;
            //用大力量的工人解决需要力量小的任务看看是否能完成，不能完成去左侧二分
            if(f(tasks,workers,0,m-1,wsize-m,wsize-1,pills,strength)){
                ans = m;
                l = m + 1;
            }else{
                r = m - 1;
            }
        }
        return ans;
    }
    public static boolean f(int[] tasks,int[] workers,int tl,int tr,int wl,int wr,int pills,int s){
        h=t=0;
        int cnt = 0;//吃药数
        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{//吃药仍不能解锁任务
                    return false;
                }
            }
        }
        return cnt <= pills;
    }
}