滑动窗口算法思想图解说明

妖狐艹你老母 2022-10-31 04:14 410阅读 0赞

# 滑动窗口算法 #

滑窗思想在解决一些联系子数组问题上被广泛应用，遇到对一些给定长度的子数组序列进行操作 或者求解子串问题，首先想到滑窗技巧

*  ### 滑窗思想模板 ###

最为经典的滑窗算法有其固定的解题模板

下面就通过一段伪代码的形式对滑窗思想进行阐述

int left = 0, right = 0;
    
    while (right < s.size()) {
        // 增大窗口
        window.add(s[right]);
        right++;
    
        while (window needs shrink) {
            // 缩小窗口
            window.remove(s[left]);
            left++;
        }
    }

*  ### 滑窗思想应用 ###

接下来通过几道算法题目对滑窗思想进行应用

*  ### 对定长子数组操作 ###
 *  **（1）子数组的最大平均值**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70][]

double findMaxAverage(int* nums, int numsSize, int k)
    {     
        int arrsum=0;     //先前 k 个元素作为一个窗口     
        for(int i=0;i<k;i++)     
        {         
            arrsum+=nums[i];     
        }     
        int maxsum=arrsum;     //滑动窗口滑动     
        for(int i=k;i<numsSize;i++)     
        {         
            arrsum=arrsum-nums[i-k]+nums[i];         
            maxsum=arrsum>maxsum?arrsum:maxsum;     
        }     
        return (double)maxsum/k; 
    }

根据定长滑窗，计算前k个数值所组成滑窗的和大小，k个为一组向后滑动即可,每次减去窗口前一个元素,加上窗口后一个元素实现窗 口后移查找.

**举例说明：考虑数组arr \[\] = \{ 5,2，-1,0,3 \}，k = 3**

![20210221181952396.png][]

![20210221182106589.png][]

![20210221182128899.png][]

基本上依靠模板进行滑窗移动，左右边界作为滑窗边界，

**左边界左移，以及右边界右移 导致滑窗尺寸变大**

**左边界右移，以及右边界左移 导致滑窗尺寸变小**

*  **（2）滑动窗口的最大值**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1][]

class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            vector<int>res;
            if(nums.size()==0)
            {
                return res;
            }
            int n=nums.size()-k+1;//窗口数
            int t=-1;//当前窗口最大值下标
            int max;//当前窗口最大值
    
            for(int i=0;i<n;i++)
            {
                if(t<i)//上个滑窗最大值不在当前窗口里 重新遍历查找
                {
                    max=nums[i];
                    for(int j=i+1;j<i+k;j++)
                    {
                        if(nums[j]>max)
                        {
                            t=j;
                            max=nums[j];
                        }
                    }
                }
                else//上个滑窗最大值在当前窗口里
                {
                    if(nums[i+k-1] >= max)//注意，此时滑动窗口移动，只新增一个数 只需要与新增的数比较即可
                    {
                        t = i+k-1;
                        max = nums[i+k-1];
                    }
                }
                res.push_back(max);
            }
            return res;
        }
    };

对于定长滑窗，可以根据整个数组长度以及滑窗长度，确定滑窗个数nums.size()-k+1

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 2][]

*  **最大子序和**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 3][]

class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            if(nums.size()==0)
            {
                return 0;
            }
            int left=0;//滑窗  左边界索引
            int right=0;//滑窗 右边界索引
    
            int cursum=nums[0];//记录当前滑窗和
            int maxsum=nums[0];
    
            while(left<=right&&right<nums.size()-1)
            {
                right++;
                if(cursum<0&&cursum<nums[right])
                {
                    //当前滑窗和<滑窗右边界单值  或者当前滑窗为负数  需要更新左边界 重新确定滑窗
                    left=right;
                    cursum=0;//当前滑窗和 归零
                }
                cursum+=nums[right];
                maxsum=maxsum>cursum?maxsum:cursum;//根据大小关系 关系maxsum
            }
            return maxsum;
        }
    };

*  ### 对于子串的操作 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 4][]

class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            int left = 0, right = 0;
            unordered_map<char, int> window;//创建哈希表存储 方便统计重复元素
            int res = 0; // 记录最长长度
    
            while (right < s.size()) {
                char c1 = s[right];
                window[c1]++;
                right++;
                // 如果 window 中出现重复字符
                // 开始移动 left 缩小窗口
                while (window[c1] > 1) {
                    char c2 = s[left];
                    window[c2]--;
                    left++;
                }
                res = max(res, right - left);//根据当前滑窗边界差值长度对res进行更新
            }
        return res;
        }
    };

**举例说明：“pwwkew”**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 5][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70]: /images/20221024/8cebc0b70619402287bcfb1b4381b100.png
[20210221181952396.png]: /images/20221024/0b0aeecb2d8a4f5d99826e277d103a79.png
[20210221182106589.png]: /images/20221024/65e4944e72e944059d2d747d15f163c3.png
[20210221182128899.png]: /images/20221024/9b257e71b9b1401ba485d512a12babb0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1]: /images/20221024/afbb220d7a024947a4711179f319c8f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 2]: /images/20221024/f344088385ad46439d09abaead5bfdd7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 3]: /images/20221024/16f0b485d4044e1cb5fa008a9813312c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 4]: /images/20221024/f5748b2b217549f187a88ae561b4b535.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 5]: /images/20221024/fd33f58a9e0241e1b630ef637180c9ec.png