算法简介

长度为 k 的窗口，即为从原数组中连续 k 位的子数组。

滑动窗口即保持窗口的长度为 k ，且窗口从 1 ~ k 不断向后移动变为 2 ~ k+1 , 3 ~ k+2，直到 n - k + 1 ~ n。

其中窗口大小不变通过将最左侧数移出窗口，右侧数移入窗口实现

时间复杂度

\(O(n)\)

实现原理

假设求滑动窗口中的最小值（最大值同理）

首先对于如下长度为 3 的窗口：

假设看 -1 和 -3：

因为 -3 在 -1 的后面，且比 -1 晚移出窗口，由于 -3 比 -1 小，所以 -1 在之后的情况下永远不可能成为最小值，即在该情况下可以不考虑 -1 ，将它移出窗口。3 和 -3 同理。

算法实例

1. 题目描述

https://www.acwing.com/problem/content/description/156/

2. AC代码

#include <bits/stdc++.h>
const int N = 1000010;

int hh,tt;
int q[N],a[N]; // q存储的是下标

int main() {
    int n,k;
    std::cin >> n >> k;
    for (int i = 1; i <= n; i ++ ) std::cin >> a[i];
    
    // 最小值
    hh = 0,tt = -1;
    for (int i = 1; i <= n; i ++ ) {
        // 左侧数移出窗口
        if(hh <= tt && i - k + 1 > q[hh]) hh ++ ;
        
        while(hh <= tt && a[q[tt]] >= a[i]) tt -- ;
        q[++ tt] = i;
        
        if(i >= k) std::cout << a[q[hh]] << ' ';
    }
    
    std::cout << "\n";
    
    // 最大值
    hh = 0,tt = -1;
    for (int i = 1; i <= n; i ++ ) {
        // 左侧数移出窗口
        if(hh <= tt && i - k + 1 > q[hh]) hh ++ ;
        
        while(hh <= tt && a[q[tt]] <= a[i]) tt -- ;
        q[++ tt] = i;
        
        if(i >= k) std::cout << a[q[hh]] << ' ';
    }
    
    return 0;
}

参考

[1] https://www.acwing.com/solution/content/97229/