题解 | #Sliding Window#

题目链接

Sliding Window

题目描述

给定一个大小为 $n$ 的数组和一个大小为 $k$ 的滑动窗口。窗口从数组的最左侧移动到最右侧，每次向右移动一个位置。你需要输出在每个窗口位置时，窗口内的最小值和最大值。

解题思路

本题是求解“滑动窗口最大/最小值”的经典问题。如果采用朴素的暴力解法，即对每个窗口都遍历一遍来寻找最值，时间复杂度将达到 $\mathcal{O}(n \cdot k)$ ，在 $n$ 和 $k$ 较大时会超时。

解决这个问题的最优方法是使用单调队列 (Monotonic Deque)，它可以将时间复杂度优化到 $\mathcal{O}(n)$ 。

单调队列是一种特殊的双端队列，其核心思想是：在将新元素加入队列时，通过维护队列的单调性，确保队首元素始终是当前有效窗口内的最值。

我们需要两个单调队列：一个用于求最小值（队列中元素对应的数组值单调递增），另一个用于求最大值（队列中元素对应的数组值单调递减）。

以求最小值的单调队列为例，其工作流程如下（队列中存储的是元素的下标）：

当我们遍历数组，处理第 $i$ 个元素 $a[i]$ 时：

维护单调性 (从队尾操作): 检查队尾的下标 $j$ 。如果 $a[j] \ge a[i]$ ，说明 $a[j]$ 作为一个更早出现的、更大的元素，已经没有可能成为未来任何窗口的最小值了（因为有更小且更晚出现的 $a[i]$ 替代它）。因此，将 $j$ 从队尾弹出。重复此过程，直到队尾元素小于 $a[i]$ 或队列为空。
元素入队 (从队尾操作): 将当前元素的下标 $i$ 加入队尾。
移除过期元素 (从队首操作): 检查队首的下标 $j$ 。如果 $j \le i-k$ ，说明 $a[j]$ 已经滑出当前窗口（当前窗口范围是 $[i-k+1, i]$ ），因此将其从队首弹出。
记录结果: 当遍历到 $i \ge k-1$ 时，第一个完整的窗口形成。此时，队首的下标就对应着当前窗口内的最小值。

求最大值的过程完全对称，只需在第一步将比较条件 $a[j] \ge a[i]$ 改为 $a[j] \le a[i]$ 即可。

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

代码

cpp
java
python

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    deque<int> min_dq, max_dq;
    vector<int> min_res, max_res;

    for (int i = 0; i < n; ++i) {
        // 维护最小值单调队列
        while (!min_dq.empty() && a[min_dq.back()] >= a[i]) {
            min_dq.pop_back();
        }
        min_dq.push_back(i);
        if (min_dq.front() <= i - k) {
            min_dq.pop_front();
        }

        // 维护最大值单调队列
        while (!max_dq.empty() && a[max_dq.back()] <= a[i]) {
            max_dq.pop_back();
        }
        max_dq.push_back(i);
        if (max_dq.front() <= i - k) {
            max_dq.pop_front();
        }

        // 记录结果
        if (i >= k - 1) {
            min_res.push_back(a[min_dq.front()]);
            max_res.push_back(a[max_dq.front()]);
        }
    }

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

    return 0;
}

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

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> minDq = new LinkedList<>();
        Deque<Integer> maxDq = new LinkedList<>();
        StringBuilder minRes = new StringBuilder();
        StringBuilder maxRes = new StringBuilder();

        for (int i = 0; i < n; i++) {
            // 维护最小值单调队列
            while (!minDq.isEmpty() && a[minDq.peekLast()] >= a[i]) {
                minDq.pollLast();
            }
            minDq.offerLast(i);
            if (minDq.peekFirst() <= i - k) {
                minDq.pollFirst();
            }

            // 维护最大值单调队列
            while (!maxDq.isEmpty() && a[maxDq.peekLast()] <= a[i]) {
                maxDq.pollLast();
            }
            maxDq.offerLast(i);
            if (maxDq.peekFirst() <= i - k) {
                maxDq.pollFirst();
            }

            // 记录结果
            if (i >= k - 1) {
                minRes.append(a[minDq.peekFirst()]).append(" ");
                maxRes.append(a[maxDq.peekFirst()]).append(" ");
            }
        }
        
        System.out.println(minRes.toString().trim());
        System.out.println(maxRes.toString().trim());
    }
}

import sys
from collections import deque

def solve():
    line = sys.stdin.readline()
    if not line: return
    n, k = map(int, line.split())
    
    line = sys.stdin.readline()
    if not line: return
    a = list(map(int, line.split()))

    min_dq, max_dq = deque(), deque()
    min_res, max_res = [], []

    for i in range(n):
        # 维护最小值单调队列
        while min_dq and a[min_dq[-1]] >= a[i]:
            min_dq.pop()
        min_dq.append(i)
        if min_dq[0] <= i - k:
            min_dq.popleft()

        # 维护最大值单调队列
        while max_dq and a[max_dq[-1]] <= a[i]:
            max_dq.pop()
        max_dq.append(i)
        if max_dq[0] <= i - k:
            max_dq.popleft()

        # 记录结果
        if i >= k - 1:
            min_res.append(a[min_dq[0]])
            max_res.append(a[max_dq[0]])

    print(*min_res)
    print(*max_res)

solve()

算法及复杂度

算法: 单调队列 / 滑动窗口
时间复杂度: 数组中的每个元素最多被压入和弹出队列一次，因此总的时间复杂度是 $\mathcal{O}(n)$ 。
空间复杂度: 队列中最多存储 $k$ 个元素的下标，因此空间复杂度为 $\mathcal{O}(k)$ 。