单调队列——滑动窗口

单调队列

什么是单调队列

说白了就是一个队列，但是队列满足单调的条件。

滑动窗口

在了解单调队列之前先看一道经典的单调队列问题——滑动窗口。

Acwing T154 单调队列

题意：

给定一个长度为n的数组，有一个长度为k的窗口从数组的左边滑向右边，每次滑动一格，求每次滑动窗口中的最大值和最小值。

输入输出示例：

输入：
8 3
1 3 -1 -3 5 3 6 7

输出：
-1 -3 -3 -3 3 3
3 3 5 5 6 7

思路

暴力循环肯定也能解决问题，但是也肯定会超时，这时候就要用单调队列

单调队列实现

维护一个队列的数据结构，随着窗口的滑动，在满足队列单调性的情况下进行入队和出队操作。

即：假设维护一个单调递增的队列，通过扫描数组读入数组的值，用head指针和tail指针维护窗口队列的最大值和最小值，当读入的数组的值num[i]小于tail指向的值的时候，则将小于num[i]的值出队，再将num[i]入队，且如果head维护的值刚好被抛出时，将head指向下一个值。

具体代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = bufferedReader.readLine().split(" ");
        String[] s2 = bufferedReader.readLine().split(" ");
        int n , k;
        n = Integer.parseInt(s1[0]);
        k = Integer.parseInt(s1[1]);
        long[] nums = new long[n];
        int[] que = new int[n];  //队列
        int head = 0;    //队头指针
        int tail = -1;   //队尾指针
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(s2[i]);
        }
        for (int i = 0; i < n; i++) {
            if(head<=tail && que[head]<i-k+1){
                head++;            //如果head指向的最大值刚好被抛出head向右移动一位
            }
            while (head<=tail && nums[que[tail]]>= nums[i]){
                tail--;     //将大于nums[i]的数据出队，即将队尾左移动
            }
            que[++tail] = i;  //将nums[i]入队
            if(i>=k-1){        //当窗口长度大于k之后输出
                System.out.print(nums[que[head]]+" ");
            }
        }
        System.out.println();
        que = new int[n];
        head = 0 ; tail = -1;
        //递减队列，同上，换个方向
        for (int i = 0; i < n; i++) {
            if(head<=tail && que [head]<i-k+1){
                head++;
            }
            while (head<=tail && nums[que[tail]]<= nums[i]){
                tail--;
            }
            que[++tail] = i;
            if(i>=k-1){
                System.out.print(nums[que[head]]+" ");
            }
        }

    }
}

使用场景

单调队列的使用场景相对较少，除了滑动窗口之外可以用单调队列进行DP优化，比如背包问题的队列优化。

本文地址：https://blog.csdn.net/weixin_43322795/article/details/110208066