题解 | #【模板】滑动窗口#

题目链接

【模板】滑动窗口

题目描述

给定一个长度为 $n$ 的整数数组和一个大小为 $k$ 的滑动窗口。窗口从数组的最左侧移动到最右侧，每次只移动一个位置。任务是，对于每个窗口位置，找出窗口内所有元素的最大值。

解题思路

这是一个经典的滑动窗口最大值问题。最朴素的想法是遍历每个窗口，再在窗口内寻找最大值，但这样做的时间复杂度为 $O(n \cdot k)$ ，在 $n$ 和 $k$ 较大时会超时。

为了高效地解决这个问题，我们可以使用一种特殊的数据结构：单调递减队列。这个队列将帮助我们在均摊 $O(1)$ 的时间内获取当前窗口的最大值。

我们使用一个双端队列（deque），里面存储的是数组元素的下标，而不是元素值。这个队列需要始终维护一个关键性质：队列中的下标所对应的数组元素是严格单调递减的。这样，队首的下标就永远对应着当前窗口内的最大值。

算法步骤如下：

初始化：创建一个空的双端队列 $dq$ 用于存储下标。
遍历数组：从左到右遍历输入数组，对于每个元素 $a[i]$ ： a. 移除队尾元素：在将新元素的下标 $i$ 入队之前，先从队尾开始检查。如果队列不为空，且队尾下标对应的元素 $a[dq.back()]$ 小于或等于当前元素 $a[i]$ ，则将队尾下标弹出。重复此过程，直到队尾元素大于当前元素，或队列为空。 * 原因：如果一个较小的元素在一个较大元素的左边，那么只要这个较大元素还在窗口内，那个较小的元素就永远不可能成为窗口最大值。因此，可以安全地将其从候选队列中移除。 b. 新元素入队：将当前元素的下标 $i$ 加入队尾。 c. 移除队首元素：检查队首的下标 $dq.front()$ 是否已经滑出当前窗口的范围（即 $dq.front() \le i - k$ ）。如果是，则将其从队首弹出。 d. 记录结果：当遍历的下标 $i$ 使得第一个完整的窗口形成时（即 $i \ge k - 1$ ），队首的下标 $dq.front()$ 就对应着当前窗口的最大值。记录 $a[dq.front()]$ 。
输出：遍历结束后，将所有记录的结果按格式输出。

由于每个元素的下标最多只入队一次、出队一次，因此整个算法的时间复杂度为线性时间 $O(n)$ 。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    deque<int> dq;
    vector<int> result;

    for (int i = 0; i < n; ++i) {
        while (!dq.empty() && a[dq.back()] <= a[i]) {
            dq.pop_back();
        }
        dq.push_back(i);

        if (dq.front() <= i - k) {
            dq.pop_front();
        }

        if (i >= k - 1) {
            result.push_back(a[dq.front()]);
        }
    }

    for (size_t i = 0; i < result.size(); ++i) {
        cout << result[i] << (i == result.size() - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        Deque<Integer> dq = new ArrayDeque<>();
        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) {
                dq.pollLast();
            }
            dq.offerLast(i);

            if (dq.peekFirst() <= i - k) {
                dq.pollFirst();
            }

            if (i >= k - 1) {
                result.add(a[dq.peekFirst()]);
            }
        }

        for (int i = 0; i < result.size(); i++) {
            System.out.print(result.get(i) + (i == result.size() - 1 ? "" : " "));
        }
        System.out.println();
    }
}

from collections import deque

n, k = map(int, input().split())
a = list(map(int, input().split()))

dq = deque()
result = []

for i in range(n):
    while dq and a[dq[-1]] <= a[i]:
        dq.pop()
    dq.append(i)

    if dq[0] <= i - k:
        dq.popleft()
    
    if i >= k - 1:
        result.append(a[dq[0]])

print(*result)

算法及复杂度

算法：单调队列。
时间复杂度： $O(n)$ ，因为数组中的每个元素最多被推入和弹出队列一次。
空间复杂度： $O(k)$ ，因为双端队列中最多存储 $k$ 个元素的下标。