算法专题整理：滑动窗口-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法专题整理：滑动窗口。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

视频课程：同向双指针滑动窗口【基础算法精讲 01】_哔哩哔哩_bilibili

滑动窗口也可以理解为双指针法的一种。

滑动窗口的核心在于连续！如果需要得到的结果是满足某种较为明显条件的连续的子数组，可以考虑使用滑动窗口来做。

通常情况下，滑动窗口是枚举右端点，然后按条件移动左端点。

枚举右端点比枚举左端点方便，因为枚举右端点，移动左端点时信息是枚举过的，是已知的；移动左端点是在缩小范围，通常更好写。

如果左端点的移动条件不明或者比较复杂，就不适合用滑动窗口。

滑动窗口一般来说，是将题目转换为求最短长度的子序列/最大长度的子序列问题，满足条件的子序列就是窗口，枚举所有窗口右端点的同时，更新左端点。

左端点的移动原则：找长度最短的窗口，就是只要满足条件就移动左端点；找长度最长的窗口，就是超范围了才移动左端点。

找长度最短的连续子序列

示例1：209.长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5

思路

本题是很经典的滑动窗口题目，选取特定条件下的连续子数组，且为找最小长度子序列问题。因此本题是只要while循环满足条件，就更新左端点，从而使得最后得到的窗口长度是最小值。

本题特定条件并不复杂，是求和的条件，并不需要单独写函数。只要满足特定条件，就可以进行滑动。

解答

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int i=0;
        int sum=0;
        int subLength=0;
        int result = INT_MAX;
        //开始滑动，直接用[i,j]作为窗口
        for(int j=0;j<nums.size();j++){
            sum += nums[j];
            //只要满足条件，就不断滑动，方便取最小值
            while(sum>=target){
                subLength = j-i+1;
                result = result<subLength?result:subLength;
                sum-=nums[i];
                i++;
            }
        }
        //如果一直没找到，结果置零
		if(result==INT_MAX){
            result=0;
        }
        return result;
    }
};

二刷记录

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        //经典滑动窗口
        int leftIndex=0;
        int sum=0;
        int subLength = 0;
        int result = INT_MAX;

        for(int i=0;i<nums.size();i++){
            sum+=nums[i];
            //rightIndex++;不需要单独的右端点，滑动窗口本身就是枚举右端点
            if(sum<target) continue;
            else{
                while(sum>=target){
                    //满足条件才会更新subLength
                    subLength = i-leftIndex+1;//记录遍历过的所有的窗口长度
                    result = (result<subLength)?result:subLength;
                    sum-=nums[leftIndex];
                    leftIndex++;
                }
            }
        }
        return (result==INT_MAX)?0:result;

    }
};

找最长的连续子序列

示例1：2779.数组的最大美丽值（转换成连续子序列最大长度）

给你一个下标从 0 开始的整数数组 nums 和一个非负整数 k 。

在一步操作中，你可以执行下述指令：

在范围 [0, nums.length - 1] 中选择一个 此前没有选过 的下标 i 。
将 nums[i] 替换为范围 [nums[i] - k, nums[i] + k] 内的任一整数。

数组的 美丽值 定义为数组中由相等元素组成的最长子序列的长度。

对数组 nums 执行上述操作任意次后，返回数组可能取得的最大美丽值。

注意： 你只能对每个下标执行一次此操作。

数组的 子序列 定义是：经由原数组删除一些元素（也可能不删除）得到的一个新数组，且在此过程中剩余元素的顺序不发生改变。

示例 1：

输入：nums = [4,6,1,2], k = 2
输出：3
解释：在这个示例中，我们执行下述操作：
- 选择下标 1 ，将其替换为 4（从范围 [4,8] 中选出），此时 nums = [4,4,1,2] 。
- 选择下标 3 ，将其替换为 4（从范围 [0,4] 中选出），此时 nums = [4,4,1,4] 。
执行上述操作后，数组的美丽值是 3（子序列由下标 0 、1 、3 对应的元素组成）。
可以证明 3 是我们可以得到的由相等元素组成的最长子序列长度。

示例 2：

输入：nums = [1,1,1,1], k = 10
输出：4
解释：在这个示例中，我们无需执行任何操作。
数组 nums 的美丽值是 4（整个数组）。

提示：

1 <= nums.length <= 105
0 <= nums[i], k <= 105

思路1：排序+滑动窗口

因为美丽值的定义是数组中由相等元素组成的最长子序列的长度，因此我们想要获得全部都是相等元素的序列，并求最大长度。

虽然本题要求 子序列 定义是剩余元素的顺序不发生改变，但是求的是相等元素组成的最长子序列长度，因此元素的顺序并不影响结果。

因此我们可以先进行排序，让相等的元素排在一起，此时只需要判断窗口左端点（最小值）和右端点（最大值）是不是相等，也就是只有nums[r]-k<=nums[l]+k的时候，才作为有效窗口。

此时，本题就转变成了，求满足nums[r]-k<=nums[l]+k条件的最长子序列，也就是找最长的连续子数组，其最大值-最小值不超过2k。

也属于找最长子序列问题。最长子序列需要枚举右端点，只有不满足条件的时候，才更新左端点。

class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int res=1;//这道题子序列是找相等元素
        for(int left=0,right=0;right<nums.size();right++){
            //因为是找最大长度，所以是不符合<=条件了，才移动左端点
            while((nums[right]-nums[left])>2*k){
                left++;
            }
            res=max(res,right-left+1);//res存放长度的最大值
        }
        return res;
    }
};

注意点

由于选的是子序列，且子序列的元素都相等，所以元素顺序对答案没有影响，可以先对数组排序。

且仔细看用例1可以看出，并不要求最后的子数组在原数组也是连续的，只是找替换后相等的数字组成的总长度，并不是找原数组中就连续的子数组！

参考题解：
灵茶山艾府
力扣周赛总结

示例2：674.最长连续递增序列（连续子序列最大长度）

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：

输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

示例 2：

输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。

提示：

1 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9

思路1：滑动窗口

本题是求连续递增子序列的长度，此时第一反应是滑动窗口。

本题和上一题：数组的最大美丽值很像，美丽值这道题目求的也是连续的最长子序列的长度，这两道题的做法类似但是有一定的区别。

本题的滑动窗口做法：

遇到不是递增的，直接更新左端点

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if(nums.size()==1) return 1;
        //开始滑动
        int res=1;
        int start=0;//先从下标0位置开始找
        for(int i=1;i<nums.size();i++){
            //只要不是递增，直接修改左端点
            if(nums[i]<=nums[i-1]){
                start=i;
            }
            res=max(res,i-start+1);//res存放长度的最大值
        }
        return res;

    }
};

滑动窗口二刷记录

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int leftIndex = 0;
        int subLength = 0;
        int result = INT_MIN;
        for(int rightIndex=0;rightIndex<nums.size()-1;rightIndex++){
            //注意：这里是rightIndex<rightIndex+1,因此长度需要从rightIndex+1开始减去左端点！
            if(nums[rightIndex]<nums[rightIndex+1]){
                cout<<nums[rightIndex]<<endl;
                subLength = rightIndex+1-leftIndex+1; //因为是与rightIndex+1做比较！
                result = (result>subLength)?result:subLength;
            }
            else{//不是连续递增了
                leftIndex = rightIndex+1; //左端点的更新是从rightIndex+1开始的
            }
        }
        return (result==INT_MIN)?1:result;
    }
};

2779.数组最大美丽值的滑动窗口做法：

排序之后找左右窗口端点值相减<=2k的窗口，并求窗口最大长度

class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int res=1;//这道题子序列是找相等元素
        for(int left=0,right=0;right<nums.size();right++){
            //因为是找最大长度，所以是不符合<=条件了，才移动左端点
            while((nums[right]-nums[left])>2*k){
                left++;
            }
            res=max(res,right-left+1);//res存放长度的最大值
        }
        return res;
    }
};

从这两个题目对比也可以看出来，滑动窗口指的是遍历右端点，按照条件移动左端点。

在最长连续递增子序列的问题中，需要找的是数组中最长的递增子序列。所以当发现当前元素不大于前一个元素时，窗口的左端点直接跳到新的位置求新的递增长度，不需要慢慢滑动。

在数组最大美丽值中，需要找的是数组中最长的由相等元素组成的子序列，且可以将数组中的元素替换为它加减k的结果。因此当发现窗口right-k大于窗口left+k时，需要将窗口的左边界进行滑动。

这两道题目的滑动窗口思想是类似的，都是通过移动窗口的左右边界来找到最长的满足某种条件的子序列。

思路2：动态规划

但是其实这个题没必要用滑动窗口，因为本题求递增子序列，左端点不用滑，只要一直枚举右端点能不能扩，断开的话将左端点移到右端点的位置即可。

本题可以像 300.最长递增子序列一样用DP解决。

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        vector<int>dp(nums.size(),1);
        if(nums.size()==1) return 1;
        //记录长度的初始值
        int res=1;
        for(int i=1;i<nums.size();i++){
            if(nums[i]>nums[i-1]){
                dp[i]=dp[i-1]+1;
            }
            res=max(res,dp[i]);//res存放dp[i]的最大值
        }
        return res;
    }
};

找满足条件的子数组个数

示例1：2762.不间断子数组

给你一个下标从 0 开始的整数数组 nums 。nums 的一个子数组如果满足以下条件，那么它是 不间断 的：

i，i + 1 ，…，j 表示子数组中的下标。对于所有满足 i <= i1, i2 <= j 的下标对，都有 0 <= |nums[i1] - nums[i2]| <= 2 。

请你返回 不间断 子数组的总数目。

子数组是一个数组中一段连续非空的元素序列。

示例 1：

输入：nums = [5,4,2,4]
输出：8
解释：
大小为 1 的不间断子数组：[5], [4], [2], [4] 。
大小为 2 的不间断子数组：[5,4], [4,2], [2,4] 。
大小为 3 的不间断子数组：[4,2,4] 。
没有大小为 4 的不间断子数组。
不间断子数组的总数目为 4 + 3 + 1 = 8 。
除了这些以外，没有别的不间断子数组。

示例 2：

输入：nums = [1,2,3]
输出：6
解释：
大小为 1 的不间断子数组：[1], [2], [3] 。
大小为 2 的不间断子数组：[1,2], [2,3] 。
大小为 3 的不间断子数组：[1,2,3] 。
不间断子数组的总数目为 3 + 2 + 1 = 6 。

提示：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9

思路

这道题目也是一道典型的滑动窗口题，要求找出所有满足特定条件的连续子数组的个数。特定条件是，对于子数组中的任意两个元素，他们的绝对值差不能超过 2。

本题定义窗口满足绝对值差<=2的条件，且题目要求子数组连续，也就是不能改变原有元素顺序，因此我们不能直接对原数组进行排序求出绝对值<=2的连续子序列。但是我们依旧可以用滑动窗口right-left+1来包含所有的，区间内的子数组的情况。

因为本题求的是符合条件的子数组的总数，所以只有令窗口最大，才能令窗口右端点-左端点+1这个长度包含所有的符合条件的情况。

因此本题可以转换为，求解满足 0 <= |nums[i1] - nums[i2]| <= 2 的最大长度的滑动窗口。

使用哈希表multiset的原因:自动找到窗口最大值/最小值

题目中要求但是排序后数组元素的顺序发生改变，会导致子数组与原数组中的子数组不再一致。

因为原题目中，要求的是子数组任意两个元素绝对值差不超过2。因此，我们就需要知道子数组的最大元素和最小元素之间的差值。

为了节省时间复杂度，防止我们每次找最大值和最小值都需要重新遍历，本题我们最好采用可重复的有序哈希表multiset/multimap来实现。

因为本题nums是存在重复元素的！因此我们只能选取key可重复的哈希表，允许重复的哈希表只有multiset和multimap。因为并不涉及次数统计，所以采用multiset。

解答

窗口实际上就是数组内的下标[left,right]，只是把这些元素都放到mset里面进行储存了。

class Solution {
public:
    long long continuousSubarrays(vector<int> &nums) {
        long long result=0;
        //创建一个multiset作为窗口，此处不是数组，因为set方便比较大小
        multiset<int>mset;
        int left=0;
        //nums.size()不是nums.end()
        for(int right = 0;right<nums.size();right++){
            //加入窗口
            mset.insert(nums[right]);
            //set默认升序，最大值在rbegin
            while(*mset.rbegin()-*mset.begin()>2){
                mset.erase(mset.find(nums[left]));
                left++;
            }
            //以right为右端点，左端点在[left,right]范围内任意一点都满足条件
            //这里的result要进行累加！
            result += right-left+1;
        }
        return result;
    }
};

如何获得[left,right]窗口内所有大小的以right为右端点的数组

因为本题需要输出所有大小的数组个数，加上是遍历right，因此我们的策略是对于每一个right，找到右端点为right的所有大小的子数组！

例如[1,2,3]，所有以right=3为右端点的子数组，就是[1,2,3][2,3],[3]

也就是说，对于每一个right，[left,right]内包括所有大小的，以right为右端点的数组个数，是right-left+1。

因此result会在每一个right遍历的时候进行累加，得到**[left,right]窗口内所有大小的数组个数**。

总结

如果题目要求的是在原数组中就连续的子数组，那么不能进行排序的操作，需要借助multiset等容器来完成窗口内部的排序。

但是如果题目求的数组，并不是必须在原数组中就连续的，就可以考虑直接排序，让符合条件的元素相邻在一起。

示例2： 2799.统计完全子数组的数目

给你一个由正整数组成的数组 nums 。

如果数组中的某个子数组满足下述条件，则称之为 完全子数组 ：

子数组中不同元素的数目等于整个数组不同元素的数目。

返回数组中 完全子数组 的数目。

子数组 是数组中的一个连续非空序列。

示例 1：

输入：nums = [1,3,1,2,2]
输出：4
解释：完全子数组有：[1,3,1,2]、[1,3,1,2,2]、[3,1,2] 和 [3,1,2,2] 。

示例 2：

输入：nums = [5,5,5,5]
输出：10
解释：数组仅由整数 5 组成，所以任意子数组都满足完全子数组的条件。子数组的总数为 10 。

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 2000

思路

首先我们需要知道有多少种不同的元素，然后使用滑动窗口的方式，一直扩大右边界，直到窗口内的元素种类与原数组相同，此时缩小左边界，每次缩小左边界，都可以对答案进行累加，因为滑动窗口内的子数组都是满足条件的。

注意，我们为了统计所有满足条件的子数组个数，滑动窗口的left左移需要同时统计map里面元素的个数。

完整版

class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        int n=nums.size();
        unordered_map<int,int>count;
        unordered_set<int>uniqueNums;
        //先得到所有元素的种类数目
        for(int num:nums){
            uniqueNums.insert(num);//uset插入元素只能用insert
            //count[num]++;count必须在窗口内部更新
        }
        int result=0;
        int left=0;
        for(int i=0;i<nums.size();i++){
            count[nums[i]]++;//nums[i]累积数目
            //元素种类相同，缩小左边界
            while(count.size()==uniqueNums.size()){
                result+=nums.size()-1-i+1;//包含所有的子数组情况
                count[nums[left]]--;
                if(count[nums[left]]==0){
                    count.erase(nums[left]);
                }
                left++;
            }
            //右边界i++包含在for循环里面了
        }
        return result;
    }
};

针对二维数组的滑动窗口

注意：如果是二维数组，那么一般都是把区间作为滑动的单位，而不是把区间里面的数字作为滑动单位！
如果区间里的每一个数字都作为滑动单位，会导致超时

示例1：⭐⭐2271. 毯子覆盖的最多白色砖块数

给你一个二维整数数组 tiles ，其中 tiles[i] = [li, ri] ，表示所有在 li <= j <= ri 之间的每个瓷砖位置 j 都被涂成了白色。

同时给你一个整数 carpetLen ，表示可以放在任何位置的一块毯子的长度。

请你返回使用这块毯子，最多可以盖住多少块瓷砖。

示例 1：

算法专题整理：滑动窗口,算法模板与专题整理,算法,leetcode,数据结构,c++

输入：tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10
输出：9
解释：将毯子从瓷砖 10 开始放置。
总共覆盖 9 块瓷砖，所以返回 9 。
注意可能有其他方案也可以覆盖 9 块瓷砖。
可以看出，瓷砖无法覆盖超过 9 块瓷砖。

示例 2：

输入：tiles = [[10,11],[1,1]], carpetLen = 2
输出：2
解释：将毯子从瓷砖 10 开始放置。
总共覆盖 2 块瓷砖，所以我们返回 2 。

提示：

1 <= tiles.length <= 5 * 10^4
tiles[i].length == 2
1 <= li <= ri <= 10^9
1 <= carpetLen <= 10^9
tiles 互相 不会重叠 。

思路

只看文本不太好理解，可以画图进行辅助：
算法专题整理：滑动窗口,算法模板与专题整理,算法,leetcode,数据结构,c++
滑动窗口是枚举右端点，然后按照规则滑动左端点。

窗口总长度sum=a+b+c，每次枚举一个右端点（也就是滑动一个二维数组的区间），sum都会加上tiles[1]-tiles[0]+1。

因为我们求的是覆盖的最长区间的长度，因此只要上个区间右端点在毛毯的范围内，上个区间就可以算进去，就不需要滑动左端点！

如果求的是最长区间长度，那么while循环条件写法是不满足条件才会滑动。

while(tile[r][1]-tile[l][1]>carpetlen){
    sum-=tile[r][1]-tile[r][0]+1;//sum本来算的就是整块区间的瓷砖，所以当左区间不满足条件，应该直接剪掉区间，sum本身就是一个区间一个区间直接累加的！
    l++;
}
//这里是更新的最大瓷砖数目，毛毯区间的最大瓷砖数 = sum(总瓷砖数)-x = sum-(tile[r][1]-tile[l][0]-carpetlen)
res = max(res,sum-max(0,tile[r][1]-tile[l][0]-carpetlen+1));
//注意，x有可能是负数，所以需要x和0取最大值

完整版

注意：sum是窗口里瓷砖长度的和！是不包括空白区域的！所以sum-x指的就是窗口内部有多少块瓷砖，同时x可能是负数，所以x要和0取最值！
从下面这个debug打印也可以看出，如果x没有和0取最值，最后得到的结果会偏大，因为减去负数了

算法专题整理：滑动窗口,算法模板与专题整理,算法,leetcode,数据结构,c++

class Solution {
public:
    int maximumWhiteTiles(vector<vector<int>>& tiles, int carpetLen) {
        //先把区间按照左端点排序，为了方便滑动窗口计数
        sort(tiles.begin(), tiles.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
            return a[0] < b[0];
        });

        int ans = 0, sum = 0;
        int l = 0, r=0;

        //枚举右端点。按条件移动左端点
        //右端点是t[r][1]
        for (r=0; r < tiles.size(); ++r) {
            sum += tiles[r][1] - tiles[r][0] + 1;
            //这里区间左边界是[l][1]，因为只要上个区间l右边界[1]在毛毯范围内，上个区间就可以算进去！
            while (tiles[l][1] <= tiles[r][1] - carpetLen) {
                sum -= tiles[l][1] - tiles[l][0] + 1;
                ++l;
            }
            ans = max(ans, sum - max(0, tiles[r][1] - carpetLen - tiles[l][0] + 1));
        }

        return ans;
    }
};

示例2：⭐小红书2023秋招提前批–精华帖

P5801 - 【二分查找】小红书2023秋招提前批-精华帖子 - 欧弟算法 (algomooc.com)

算法专题整理：滑动窗口,算法模板与专题整理,算法,leetcode,数据结构,c++
文章来源地址https://www.toymoban.com/news/detail-530067.html

完整版

本题基本上和上面地砖那道题一模一样了，截取长度就是毛巾长度，最多的精华帖子数量就是瓷砖数目。
标记的是帖子区间，所以帖子区间就是对应的上面一题白色瓷砖的区间。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<pair<int, int>> e(m);
    for (int i = 0; i < m; ++i) {
        cin >> e[i].first >> e[i].second;
    }
    
    // Sorting
    sort(e.begin(), e.end(), [](const pair<int, int>& x, const pair<int, int>& y) {
        return x.first < y.first;
    });
    
    int ans = 0, sum = 0;
    
    // Sliding window (enumerate the right endpoint, try to move the left endpoint)
    for (int l = 0, r = 0; r < m; ++r) {
        sum += e[r].second - e[r].first;
        // Remove the excess
        while (e[r].second - e[l].second > k) {
            sum -= e[l].second - e[l].first;
            l++;
        }
        // Check if the first interval is completely occupied
        if (e[r].second - k > e[l].first) {
            ans = max(ans, sum - (e[r].second - k - e[l].first));
        } else {
            ans = max(ans, sum);
        }
    }
    
    cout << ans << endl;
    return 0;
}