单调队列-上

题目1（单调队列经典用法模板）

题目链接：239. 滑动窗口最大值

做法

1. 维护一个单调递减的双端队列，队列存处的是数组的索引
   • 队首元素始终是当前窗口最大值的索引
   • 队列中索引对应的值依次递减
2. 先按上述要求构造长度为k-1的队列，对于窗口[l,r]，
   • 首先添加右边界元素r（维护单调性）
   • 记录答案，即队首元素对应数组中的值
   • 移除左边界元素（队首索引等于窗口左边界l则移除）

代码

class Solution {
    public static int MAXN = 100001;
    public static int[] deque = new int[MAXN];
    public static int h,t;//队列头，尾
    public int[] maxSlidingWindow(int[] nums, int k) {
        h=t=0;
        int n = nums.length;
        //先构造长度为k-1的双端队列
        for(int i = 0;i < k-1;i++){
            //不遵循大->小，从左边出队列
            while(h < t && nums[deque[t-1]] <= nums[i]){
                t--;
            }
            deque[t++] = i;
        }
        int m = n - k + 1;//由题意得到的答案数组长度
        int[] ans = new int[m];
        //对于上面构造的长度为k-1的队列，先从右边加一个，记录答案，再从左边减一个
        for(int l = 0,r = k - 1;l < m;l++,r++){
             while(h < t && nums[deque[t-1]] <= nums[r]){
                t--;
             }
             deque[t++] = r;
             ans[l] = nums[deque[h]];//记录答案
             if(deque[h] == l){
                h++;
             }
        }
        return ans;
    }
}

题目2

题目链接:1438. 绝对差不超过限制的最长连续子数组

做法

1. 对于一个不满足要求的子数组而言，向右拓宽子数组只会更不满足（最大值更大或不变，最小值更小或不变）
2. 维护两个单调队列用于记录某一窗口的最大值和最小值，思路同上题
3. 遍历原数组，用l,r维护滑动窗口，r永远是滑动窗口没有添加的下一个数的位置，添加到直至不满足要求为止，此时记录答案，弹出队首，继续添加到不满足要求为止

代码

class Solution {
    public static int MAXN = 100001;
    public static int[] maxDeque = new int[MAXN];//单调递减队列用于找最大值
    public static int[] minDeque = new int[MAXN];//单调递减队列用于找最大值
    public static int maxh,maxt,minh,mint;
    public static int[] arr;
    public int longestSubarray(int[] nums, int limit) {
        maxh=minh=maxt=mint=0;
        arr = nums;
        int n = arr.length;
        int ans = 0;
        for(int l = 0,r = 0;l < n;l++){
            while(r < n&& ok(limit,arr[r])){
                push(r++);
            }
            ans = Math.max(ans,r-l);
            pop(l);
        }
        return ans;
    }
    //加入number还是否满足条件
    public static boolean ok(int limit,int number){
        int max = maxh < maxt ? Math.max(arr[maxDeque[maxh]],number) : number;
        int min = minh < mint ? Math.min(arr[minDeque[minh]],number) : number;
        return (max - min) <= limit;
    }
    //将下标r对应的值加到队列中
    public static void push(int r){
        while(maxh < maxt && arr[maxDeque[maxt-1]] <= arr[r]){
            maxt--;
        }
        maxDeque[maxt++] = r;
        while(minh < mint && arr[minDeque[mint-1]] >= arr[r]){
            mint--;
        }
        minDeque[mint++] = r;
    }
    //弹出队首
    public static void pop(int l){
        if(maxDeque[maxh] == l){
            maxh++;
        }
        if(minDeque[minh] == l){
            minh++;
        }
​
    }
}

题目3

**题目链接:P2698 [USACO12MAR] Flowerpot S - 洛谷**

做法同上

package com.study.class54;
​
import java.io.*;
import java.util.Arrays;
​
public class Main {
    public static int MAXN = 100001;
    public static int[][] arr = new int[MAXN][2];
    public static int[] maxDeque =  new int[MAXN];
    public static int[] minDeque =  new int[MAXN];
    public static int maxh,maxt,minh,mint;
    public static int n,d;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while(in.nextToken() != StreamTokenizer.TT_EOF){
            n = (int) in.nval;
            in.nextToken();
            d = (int) in.nval;
            for(int i = 0; i < n; i++){
                in.nextToken();
                arr[i][0] = (int) in.nval;
                in.nextToken();
                arr[i][1] = (int) in.nval;
            }
            int ans = compute();
            out.println(ans == Integer.MAX_VALUE ? -1 : ans);
        }
    br.close();
    out.close();
    out.flush();
    }
    public static int compute(){
        Arrays.sort(arr, 0, n, (a, b) -> a[0] - b[0]);
        maxh=maxt=minh=mint=0;
        int ans = Integer.MAX_VALUE;
        for(int l=0,r=0;l<n;l++){
            while(r<n&&!ok()){
                push(r++);
            }
            if(ok()){
                ans = Math.min(ans,arr[r-1][0] - arr[l][0]);
            }
            pop(l);
        }
​
        return ans;
    }
    public static  boolean ok(){
        int max = maxh < maxt ? arr[maxDeque[maxh]][1] : 0;
        int min = minh < mint ? arr[minDeque[minh]][1] : 0;
        return (max - min) >= d;
    }
    public static void push(int r){
        while(maxh < maxt && arr[maxDeque[maxt-1]][1] <= arr[r][1]){
            maxt--;
        }
        maxDeque[maxt++] = r;
        while(minh < mint && arr[minDeque[mint-1]][1] >= arr[r][1]){
            mint--;
        }
        minDeque[mint++] = r;
    }
    public static void pop(int l){
        if(maxDeque[maxh] == l){
           maxh++;
        }
        if(minDeque[minh] == l){
            minh++;
        }
    }
}
​