知识文档站

Appearance

单调队列-上

基本介绍 ​

应用场景 ​

滑动窗口在滑动时，r++ 代表右侧数字进窗口，l++ 代表左侧数字出窗口 ​

这个过程中，想随时得到当前滑动窗口的最大值或者最小值 ​

窗口滑动的过程中，单调队列所有调整的总代价为 O（n），单次操作的均摊代价为 O（1） ​

⚠️ 注意

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

模板思路 ​

⚠️ 注意：队列中存储的是元素的下标索引，以下的思路描述是求滑动窗口最大值的情况，即从队头到队尾存储下标对应的元素大小依次从大到小排序，使用数组实现队列，优化常数时间 ​

窗口 [ l，r ) 为左闭右开，即 r 指向窗口末尾元素的下一个位置，并且取不到，窗口长度为 r - l ​

（1）最大值或者最小值总是维护在窗口的左端点，即 l 位置 ​

（2）r++，队尾吸纳元素，只要破坏了队列中的单调性，就从队尾一直弹出元素，直到该元素能入队列并且不破坏队列中的单调性，元素相等也要弹出 ​

（3）l++，队首元素出队，新的队头继续维护最大值或者最小值 ​

滑动窗口的最大值 ​

题目链接 ​

https://leetcode.cn/problems/sliding-window-maximum/ ​

思路分析 ​

首先构造出 k - 1 长度的窗口，右边吸纳元素，收集答案，左边吐出元素，准备吸纳下一个元素，即准备收集第二个窗口的答案，以此类推，模拟题目的收集过程 ​

代码实现 ​

java
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int MAXN = 100001;
        // [l，r）左闭右开，队尾指针指向队尾元素的下一个位置
        int[] deque = new int[MAXN];
        // 队头指针
        int h = 0;
        // 队尾指针
        int 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];
        // [l，r）左闭右开，k-1 长度的窗口，r++ 收集答案，l++ 吐出元素
        for (int l = 0, r = k - 1; l < m; l++, r++) {
            // t-1 下标才是队尾元素
            while (h < t && nums[deque[t - 1]] <= nums[r]) {
                t--;
            }
            deque[t++] = r;
            // 收集答案
            ans[l] = nums[deque[h]];
            // l 位置的数出去
            if (deque[h] == l) {
                h++;
            }
            // 例如数组 [5 6 3 ...]，初始 k-1 的窗口为 [6]，l 指向 5，r 指向 3
            // 窗口左闭右开 [l，r），r++，3 进窗口，窗口为 [6 3]，l++，5 出窗口
            // 但不能使 l++，此时 l 指向的是 6，并没有出窗口，5 在之前就没了
            // 所以 l 时候能加加，得判断 l 位置的元素和队头位置元素的值是否相等
        }
        return ans;
    }
}

绝对值 <= limit 的最长子数组 ​

题目链接 ​

https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/ ​

思路分析 ​

使用两个队列来维护当前窗口的最大值和最小值，根据如下结论，显然有单调性，使用滑动窗口 ​

根据下面的结论，窗口变小才有可能使得 max - min <= limit，如果当前窗口不符合条件，l++ 缩小窗口，此时才有可能是符合条件的，如果符合条件，继续 r++ 收集答案 ​

⭐ 结论

对于滑动窗口，窗口变大会让 max 更大，min 更小，窗口变小会让 max 更小，min 更大 ​

代码实现 ​

java
class Solution {
    int MAXN = 100001;

    // 窗口内最大值的更新结构（单调队列）
    int[] maxDeque = new int[MAXN];

    // 窗口内最小值的更新结构（单调队列）
    int[] minDeque = new int[MAXN];

    // 队头与队尾指针
    int maxh = 0, maxt = 0, minh = 0, mint = 0;

    int[] arr;

    public int longestSubarray(int[] nums, int limit) {
        arr = nums;
        int n = arr.length;
        int ans = 0;
        for (int l = 0, r = 0; l < n; l++) {
            // 窗口 [l，r）左闭右开，如果当前窗口不符合条件
            // 根据结论应当缩小窗口，如果符合，继续扩大窗口
            while (r < n && ok(limit, nums[r])) {
                push(r++);
            }
            // 此时窗口 [l，r），长度为 r - l
            ans = Math.max(ans, r - l);
            // while 出来说明再扩大窗口就不符合条件了
            // 记录此时的答案，缩小窗口，判断是否符合
            pop(l);
        }
        return ans;
    }

    // 判断当前窗口是否符合 max - min <= limit
    public boolean ok(int limit, int number) {
        // 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;
    }

    // 窗口 [l，r）左闭右开，r 位置的数取不到
    public 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;
    }

    // 吐出窗口 l 位置的数，注意判断 deque[h] == l
    public void pop(int l) {
        if (maxh < maxt && maxDeque[maxh] == l) {
            maxh++;
        }
        if (minh < mint && minDeque[minh] == l) {
            minh++;
        }
    }
}

接取落水的最小花盆 ​

题目链接 ​

https://www.luogu.com.cn/problem/P2698 ​

思路分析 ​

离散化技巧：对所有雨滴所在的位置下标排序，其他位置都是没有用的 ​

本题问的是在一个范围内，最大与最小的差值，这个范围就是一个窗口，显然使用单调队列维护最大和最小，思路和上题类似 ​

代码实现 ​

java
import java.io.*;
import java.util.Arrays;

public class Main {

    public static int MAXN = 100005;

    // arr[i] -> [雨滴位置，雨滴下落时间]
    public static int[][] arr = new int[MAXN][2];

    public static int n, d;

    public static int[] maxDeque = new int[MAXN];

    public static int[] minDeque = new int[MAXN];

    public static int maxh, maxt, minh, mint;

    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);
        }
        out.flush();
        out.close();
        br.close();
    }

    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++) {
            // [l，r）左闭右开，表示水滴的编号
            // l 表示花盆的左边界，arr[l][0]
            while (r < n && !ok()) {
                push(r++);
            }
            // while 结束的原因可能是不 ok 或者后面没有雨滴了
            // 所以这里要判断一下，有雨滴且符合条件时才更新答案
            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 (maxh < maxt && maxDeque[maxh] == l) {
            maxh++;
        }
        if (minh < mint && minDeque[minh] == l) {
            minh++;
        }
    }
}

Copyright © 2025 Jackson 凌 All Rights Reserved. | 粤ICP备2025441629号-1