算法简介
长度为 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;
}