--- ##### 啥是滑动窗口滑动窗口是基于双指针的一种思想，这类题通常是用单调双端队列辅助实现的。与单调栈类似，适用于适用于求子序列最值或目标值问题。在窗口滑动过程中，一侧作为出口，另一侧作为入口，就像队列出队入队一样，但时刻维护队列中的单调性。话不多说，上个例子就明白了。 --- ##### 例题剑指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] ![](https://content.hackertalk.net/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优化的前提下建议用数组模拟双端队列，效率更高） ```cpp class Solution { public: vector maxSlidingWindow(vector& nums, int k) { deque que; vector ans; for(int i=0; i 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 + 数组模拟哈希表）** ```cpp #include #include using namespace std; const int N = 1e5 + 10; typedef pair PII; //第一个int存到达时间，第二个int存乘客国籍 int n, v[3*N], ans; deque que; int main() { cin >> n; for(int i=0; i> 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> x; if(!v[x]) ans ++; v[x] ++; que.push_back({t, x}); } cout << ans << endl; } return 0; } ``` --- 你学fei了吗？ **（转载请注明出处，侵权必究）**