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

题目链接

【模板】滑动窗口

题目描述

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

输入:

第一行输入两个整数 $n$ 和 $k$ 。
第二行输入 $n$ 个整数，表示数组 $a$ 。

输出:

输出一行 $n-k+1$ 个整数，为每个滑动窗口的最大值，数之间以单个空格分隔。

解题思路

这是一个经典的滑动窗口最大值问题，可以使用单调队列来高效解决。

单调队列是一种特殊的队列，其内部元素保持单调性（单调递增或单调递减）。对于此题，我们需要一个单调递减的队列，用于存储数组元素的下标。队列的头部始终是当前窗口内最大值的下标。

算法步骤如下：

我们使用一个双端队列（deque）来作为单调队列。
遍历数组 $a$ 的每个元素，下标为 $i$ ： a. 队尾操作：当队列不为空，且当前元素 $a[i]$ 大于等于队尾下标对应的元素 $a[\text{q.back()}]$ 时，持续将队尾元素出队。这样可以保证队列的单调递减性。 b. 入队：将当前元素的下标 $i$ 加入队尾。 c. 队首操作：检查队首的下标是否已经滑出窗口范围（即队首下标 $\le i - k$ ）。如果是，则将队首元素出队。 d. 记录结果：当遍历过的元素个数达到 $k$ （即 $i \ge k - 1$ ）时，当前窗口形成。此时，队首元素就是当前窗口最大值的下标，将其对应的值 $a[\text{q.front()}]$ 存入结果中。

通过这种方式，每个元素的下标最多入队一次、出队一次，因此总的时间复杂度为 $\mathcal{O}(n)$ 。

代码

cpp
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> q; // 存储下标，保持对应值的单调递减
    vector<int> result;

    for (int i = 0; i < n; ++i) {
        // 移除所有小于当前元素的队尾下标，以保持单调性
        while (!q.empty() && a[q.back()] <= a[i]) {
            q.pop_back();
        }
        // 将当前元素下标入队
        q.push_back(i);

        // 移除已经滑出窗口的队首下标
        if (q.front() <= i - k) {
            q.pop_front();
        }

        // 当窗口形成后，记录最大值
        if (i >= k - 1) {
            result.push_back(a[q.front()]);
        }
    }

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

    return 0;
}

import java.util.Scanner;
import java.util.Deque;
import java.util.LinkedList;
import java.util.ArrayList;

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> q = new LinkedList<>(); // 存储下标
        ArrayList<Integer> result = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            // 移除所有小于当前元素的队尾下标
            while (!q.isEmpty() && a[q.peekLast()] <= a[i]) {
                q.pollLast();
            }
            // 将当前元素下标入队
            q.offerLast(i);

            // 移除已经滑出窗口的队首下标
            if (q.peekFirst() <= i - k) {
                q.pollFirst();
            }

            // 当窗口形成后，记录最大值
            if (i >= k - 1) {
                result.add(a[q.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()))

q = deque()  # 存储下标
result = []

for i, val in enumerate(a):
    # 移除所有小于当前元素的队尾下标
    while q and a[q[-1]] <= val:
        q.pop()
    # 将当前元素下标入队
    q.append(i)

    # 移除已经滑出窗口的队首下标
    if q[0] <= i - k:
        q.popleft()

    # 当窗口形成后，记录最大值
    if i >= k - 1:
        result.append(a[q[0]])

print(*result)

算法及复杂度

算法：单调队列
时间复杂度： $\mathcal{O}(n)$ ，因为数组中的每个元素最多被入队和出队一次。
空间复杂度： $\mathcal{O}(n)$ ，主要空间开销是输入数组和结果数组，单调队列最多存储 $k$ 个元素，在最坏情况下 $k$ 可以等于 $n$ 。