【基础算法】滑动窗口！

---

啥是滑动窗口

滑动窗口是基于双指针的一种思想，这类题通常是用单调双端队列辅助实现的。与单调栈类似，适用于适用于求子序列最值或目标值问题。在窗口滑动过程中，一侧作为出口，另一侧作为入口，就像队列出队入队一样，但时刻维护队列中的单调性。话不多说，上个例子就明白了。

---

例题 剑指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]

提示：

你可以假设 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了吗？

（转载请注明出处，侵权必究）