【单调队列】滑动窗口「单调队列经典应用」

题目

给定一个大小为 $n \le 10^6$ 的数组。

有一个大小为 $k$ 的滑动窗口，它从数组的最左边移动到最右边。

你只能在窗口中看到 $k$ 个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子：

该数组为 [1 3 -1 -3 5 3 6 7]， $k$ 为 $3$ 。

窗口位置	最小值	最大值
[1 3 -1] -3 5 3 6 7	-1	3
1 [3 -1 -3] 5 3 6 7	-3	3
1 3 [-1 -3 5] 3 6 7	-3	5
1 3 -1 [-3 5 3] 6 7	-3	5
1 3 -1 -3 [5 3 6] 7	3	6
1 3 -1 -3 5 [3 6 7]	3	7

你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数 $n$ 和 $k$ ，分别代表数组长度和滑动窗口的长度。

第二行有 $n$ 个整数，代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出，从左至右，每个位置滑动窗口中的最小值。

第二行输出，从左至右，每个位置滑动窗口中的最大值。

输入样例：

8 3
1 3 -1 -3 5 3 6 7

输出样例：

-1 -3 -3 -3 3 3
3 3 5 5 6 7

解题

方法一：单调队列

思路

单调队列通用思路：暴力求解思路 → 找单调性 → 把队列中无用元素删除形成单调队列 → 极值从队头或队尾取

使用一个队列来维护窗口，窗口往右移就是队头出队+队尾进队，暴力求窗口最大/最小值的做法是直接枚举队列中所有值，总时间复杂度是 $O(nk)$ 。

以求窗口最小值为例，在窗口中存在 $j < i$ 且 $nums[j] \ge nums[i]$ ，因为且 $nums[j]$ 比 $nums[i]$ 更大，所以只要 $nums[i]$ 存在于窗口中， $nums[j]$ 就永远不会作为最小值被输出，而 $nums[j]$ 还在 $nums[i]$ 的左边这意味着 $nums[j]$ 会更早的出队，那么 $nums[j]$ 在队列中就没有存在价值可以被删掉。

根据上面思路的具体做法是，在每次窗口右移当前元素入队之前，从队尾开始向队头枚举，如果枚举到了比当前元素大的数就把该元素出队直到不符合条件为止（删掉队列中所有逆序对），然后把当前元素从队尾入队，此时队列是单调上升的，所以窗口中的最小值就是队头元素。

求窗口最大值是镜像操作。

注意：不要让单调队列维护的窗口元素超过 k，具体来说，队列中维护下标，那么队头元素一定是窗口的起始下标，设当前遍历到的下标为 i，如果 i - que.front == k 就说明队列维护的窗口此时过大了，队头元素该出队了。

代码

数组模拟队列：

#include <iostream>

using namespace std;

const int N = 1e6 + 10;
int a[N], n, k;
int que[N], hh, tt = -1;

int main () {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    for (int i = 0; i < n; ++i) {
        if (hh <= tt && i - que[hh] == k) ++hh;
        while (hh <= tt && a[que[tt]] >= a[i]) --tt;
        que[++tt] = i;
        if (i >= k - 1) printf("%d ", a[que[hh]]);
    }
    puts("");
    hh = 0, tt = -1;
    for (int i = 0; i < n; ++i) {
        if (hh <= tt && i - que[hh] == k) ++hh;
        while (hh <= tt && a[que[tt]] <= a[i]) --tt;
        que[++tt] = i;
        if (i >= k - 1) printf("%d ", a[que[hh]]);
    }
    
    return 0;
}

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

public class Main {
    static final int N = (int) 1e6 + 10;
    static int hh = 0, tt = -1;
    static int[] que = new int[N];
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int k = (int) in.nval;
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            a[i] = (int) in.nval;
        }
        for (int i = 0; i < n; ++i) {
            if (hh <= tt && i - que[hh] + 1 > k) ++hh;
            while (hh <= tt && a[i] <= a[que[tt]]) --tt;
            que[++tt] = i;
            if (i >= k - 1) System.out.print(a[que[hh]] + " ");
        }
        System.out.print("\n");
        hh = 0;
        tt = -1;
        for (int i = 0; i < n; ++i) {
            if (hh <= tt && i - que[hh] + 1 > k) ++hh;
            while (hh <= tt && a[i] >= a[que[tt]]) --tt;
            que[++tt] = i;
            if (i >= k - 1) System.out.print(a[que[hh]] + " ");
        }
    }
}

使用 API 中的双端队列：

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

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int k = (int) in.nval;
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            a[i] = (int) in.nval;
        }
        Deque<Integer> deq = new LinkedList<>();
        for (int i = 0; i < n; ++i) {
            if (deq.size() > 0 && i - deq.peek() >= k) deq.poll();
            while (deq.size() > 0 && a[deq.peekLast()] >= a[i]) deq.pollLast();
            deq.offer(i);
            if (i >= k - 1) System.out.print(a[deq.peek()] + " ");
        }
        System.out.println();
        deq.clear();
        for (int i = 0; i < n; ++i) {
            if (deq.size() > 0 && i - deq.peek() >= k) deq.poll();
            while (deq.size() > 0 && a[deq.peekLast()] <= a[i]) deq.pollLast();
            deq.offer(i);
            if (i >= k - 1) System.out.print(a[deq.peek()] + " ");
        }
    }
}

目录CONTENT

【单调队列】滑动窗口「单调队列经典应用」

题目

解题

方法一：单调队列

思路

代码

评论区