啥是滑动窗口
滑动窗口是基于双指针的一种思想，这类题通常是用单调双端队列辅助实现的。与单调栈类似，适用于适用于求子序列最值或目标值问题。在窗口滑动过程中，一侧作为出口，另一侧作为入口，就像队列出队入队一样，但时刻维护队列中的单调性。话不多说，上个例子就明白了。
例题 剑指Offer 59 - I 滑动窗口的最大值
https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
【题目描述】
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
/pub/vXZwqx-eka0NKZ)
提示：
你可以假设 k 总是有效的，在输入数组 不为空 的情况下，1 ≤ k ≤ nums.length
思路分析
当使用暴力做法时，每次窗口弹出一个元素，又引进一个元素后，就需要对窗口内所有元素求一次最大值，每一次求最大值都需要O(n)的时间代价，所以整个暴力算法的时间复杂度为O(n²)。
在窗口内元素个数不足k个时，不作任何取最值操作，但因为所求是窗口最大值，因此辅助队列中的所有元素则需要时刻维持单调递减，当窗口内元素个数满足k个时，队列的对头即为当前窗口的最大值，求取最大值这一步骤的时间代价优化为了O(1)，极大地降低了暴力做法的时间复杂度，使整体的时间复杂度优化至接近线性。
示例模拟
当前nums = [1,3,-1,-3,5,3,6,7]，窗口大小为3
元素1进入后，当前窗口为[1]，当前队列为[1]
元素3进入后，当前窗口为[1, 3]，因需维持单调递减性，则队列弹出对头元素1，再将元素3入队，当前队列为[3]
元素-1进入后，当前窗口为[1, 3, -1]， 当前队列为[3, -1]，当前窗口内元素个数满足3个，则当前窗口的最大值即为队列的队头元素，即3，存入结果集。
元素-3进入后，当前窗口为[3, -1, -3]，当前队列为[3, -1, -3]，当前窗口内元素个数满足3个，则最大值为队头元素，即3，存入结果集。
......
直到遍历结束，将结果集返回。
C++代码
（STL中deque用法，在不开O2优化的前提下建议用数组模拟双端队列，效率更高）
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> que;
vector<int> ans;
for(int i=0; i<nums.size(); i++)
{
if(!que.empty() && i-k+1 > que.front()) que.pop_front(); //新的来，旧的去
while(!que.empty() && nums[i] >= nums[que.back()]) que.pop_back(); //维持单调递减性
que.push_back(i); //新的来
if(i+1 >= k) ans.push_back(nums[que.front()]); //最大值即为队头，放入结果集
}
return ans;
}
};
实战 [NOIP2016 普及组] 海港
https://www.luogu.com.cn/problem/P2058
题目描述
小 K 是一个海港的海关工作人员，每天都有许多船只到达海港，船上通常有很多来自不同国家的乘客。
小 K 对这些到达海港的船只非常感兴趣，他按照时间记录下了到达海港的每一艘船只情况；对于第 i 艘到达的船，他记录了这艘船到达的时间 ti (单位：秒)，船上的乘客数 ki，以及每名乘客的国籍 xi,1, xi,2, ... , xi,k
小K统计了 n 艘船的信息，希望你帮忙计算出以每一艘船到达时间为止的 24 小时（24小时 = 86400 秒）内所有乘船到达的乘客来自多少个不同的国家。
形式化地讲，你需要计算 n 条信息。对于输出的第 i 条信息，你需要统计满足 ti - 86400 < tp <= ti 的船只 p ，在所有的 xp,j 中，总共有多少个不同的数。
输入格式
第一行输入一个正整数 n，表示小 K 统计了 n 艘船的信息。
接下来 n 行，每行描述一艘船的信息：前两个整数 ti 和 ki 分别表示这艘船到达海港的时间和船上的乘客数量，接下来 ki 个整数 xi,j 表示船上乘客的国籍。
保证输入的 ti 是递增的，单位是秒；表示从小 K 第一次上班开始计时，这艘船在第 ti 秒到达海港。
输出格式
输出 n 行，第 i 行输出一个整数表示第 i 艘船到达后的统计信息。
输入样例
3
1 4 4 1 2 2
2 2 2 3
10 1 3
输出样例
3
4
4
【样例解释 】
第一艘船在第 1 秒到达海港，最近 24 小时到达的船是第一艘船，共有 4 个乘客，分别是来自国家 4,1,2,2 共来自 3 个不同的国家；
第二艘船在第 2 秒到达海港，最近 24 小时到达的船是第一艘船和第二艘船，共有 4 + 2 = 6 个乘客，分别是来自国家 4,1,2,2,2,3，共来自 4 个不同的国家；
第三艘船在第 10 秒到达海港，最近 24 小时到达的船是第一艘船、第二艘船和第三艘船，共有 4+2+1=7 个乘客，分别是来自国家 4,1,2,2,2,3,3，共来自 4 个不同的国家。
数据范围
1 ≤ n ≤ 105
∑ki ≤ 3 ∗105
1 ≤ xi,j ≤ 105
1 ≤ ti ≤ 109
思路分析
根据题意，能够提炼出滑动窗口的模型，但具体实现上则需要确定窗口的元素对象。若是将船作为窗口内的元素，那么在滑动的过程中如何处理乘客的国籍信息呢？思来想去只能暴力求取，这么做的时间代价太大了。
若选择将乘客作为窗口内的元素，由于船只到达时间是单调递增的，因此到达时间可以作为乘客所乘船的标识，那么我们可以用一个二元组存储乘客的船只到达时间和国籍信息，利用哈希表筛选国籍信息。在窗口滑动过程中，利用24小时的时间条件作为窗口大小，将不满足时间条件的船只乘客弹出队列，同时哈希表去掉相应的国籍，而新满足条件的船只，将该船所有乘客入队，并加入哈希表更新国籍信息。哈希表大小代表当前国籍数量，输出即可。
C++代码（STL中deque + 数组模拟哈希表）
#include<iostream>
#include<deque>
using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> PII; //第一个int存到达时间，第二个int存乘客国籍
int n, v[3*N], ans;
deque<PII> que;
int main()
{
cin >> n;
for(int i=0; i<n; i++)
{
int t, k;
cin >> t >> k;
while(!que.empty() && que.front().first <= t - 86400)
{
v[que.front().second] --;
if(!v[que.front().second]) ans --;
que.pop_front();
}
for(int j=0; j<k; j++)
{
int x;
cin >> x;
if(!v[x]) ans ++;
v[x] ++;
que.push_back({t, x});
}
cout << ans << endl;
}
return 0;
}
你学fei了吗？
（转载请注明出处，侵权必究）
