滑动窗口篇——如行云流水般的高效解法与智能之道（2）

前言：

上篇我们介绍了滑动窗口的含义并结合基础题型加以练习，本篇将以进阶难度的题目为索引，深化对于滑动窗口的运用与理解。

 一. 将x减到0的最小操作数

题目链接：1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

题目分析：

1. 题目要求我们每次只能从最左侧或最右侧来进行删除，且要求在原数组上直接进行修改，以满足后续操作。

2. 如果元素之和和恰好等于x，则返回最小操作数，如果不存在满足情况，则返回-1.

3. 题中提到数组内每个元素都为正整数，但target的大小不确定。

思路讲解：

  该题的困难之处在于感到无从下手，每次操作为左侧还是右侧的不确定性，采用遍历时的恐怖时间复杂度，都让我们苦不堪言。

 这时，不妨采取正难则反的思路。

1, 我们令数组内每个元素相加，和为sum，题目的要求可转化为求一段最长的连续区间，满足和为sum-x。

2. 转化之后，则可根据连续区间的性质，利用滑动窗口求解。

滑动窗口： 

我们定义flag为数组内所有元素相加之后减去x的值，那么问题已然转化为求一段最长的连续区间，满足和与flag相等，也就是我们熟悉的滑动窗口。

1. 进窗口：由于此时每一个元素都大于0，所以在窗口内增加元素，总和必然增大，因此在sum<flag时，right保持++即可，在总和sum与flag相等时，更新区间长度。

2. 出窗口：当sum>flag时，说明区间过长，此时left++即可，避免大量冗余遍历。

注意：我们在第一节谈到滑动窗口的核心三步骤为进窗口，出窗口，更新情况。

三者并无严格的先后关系，需要根据实际情况灵活运用！！！ 

代码实现：

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int flag=0,sum=0,len=-1;
        int n=nums.size();
        for(auto e:nums)
        {
            flag+=e;
        }//所有元素相加
        if(flag<x)
        {
            return -1;
        }//不存在符合情况
        flag-=x;//求取连续区间之和需满足的值
        
        for(int left=0,right=0;right<n;right++)
        {
            sum+=nums[right];//进窗口
            while(sum>flag)
            {
                sum-=nums[left++];
            }//出窗口
            if(sum==flag)
            {
                len=max(len,right-left+1);
            }//更新情况

        }
        if(len==-1)
        {
            return -1;
        }//没有满足的情况
        else
        {
            return n-len;
        }
        
    }
};

注意：如果不判定flag<x的情况，则会陷入死循环，因为此时flag为负数，while循环内left会一直++。 

二. 水果成篮

题目链接：904. 水果成篮 - 力扣（LeetCode）

题目分析：

题目较长，我们先理解给出了哪些条件和题目所求是什么：

1. 有一个数组，每一个元素的值代表水果种类

2. 有两个篮子，只能取两种类型的水果，每一棵树最多只能取一个水果。

3. 当遇到与两个篮子类型都不同的水果时，需要立即停止。反之则可以继续一直往后遍历采集 

4. 求可以采摘的最多水果数。

下面我们来具体分析：

 1. 水果种类匹配问题，不难想到采用哈希映射

 2. 采摘过程也是一个连续的区间，且也满足单调性，在该种情况下，如果向右采摘成功，水果总数必然增加，因此可以考虑在控制好种类匹配的基础上，使用滑动窗口进行解决。

思路讲解：

滑动窗口需满足，窗口内的水果种类数只有两种。

1. 采用哈希表记录水果的种类和数量，在种类小于2时，right侧可继续往后遍历，进窗口。

2. 当种类大于2时，left侧需要向后遍历出窗口，如果该水果对应的哈希表等于0时，代表种类减少了一种，需要及时改变记录。

 流程如下：

a. 初始化哈希表 hash 来统计窗⼝内⽔果的种类和数量；
b. 初始化变量：左右指针 left = 0，right = 0，记录结果的变量 ret = 0；
c. 当 right ⼩于数组⼤⼩的时候，⼀直执⾏下列循环：
i. 将当前⽔果放⼊哈希表中；
ii. 判断当前⽔果进来后，哈希表的⼤⼩：
• 如果超过 2：
◦ 将左侧元素滑出窗⼝，并且在哈希表中将该元素的频次减⼀；
◦ 如果这个元素的频次减⼀之后变成了 0，就把该元素从哈希表中删除；
◦ 重复上述两个过程，直到哈希表中的⼤⼩不超过 2；
iii. 更新结果 ret；
iv. right++，让下⼀个元素进⼊窗⼝；
d. 循环结束后，ret 存的就是最终结果

代码实现：

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int hash[100001]={0};//模拟哈希
        int kind=0;//记录水果种类
        int nums=0;//记录水果个数
        for(int left=0,right=0;right<fruits.size();right++)
        {
            if(hash[fruits[right]]==0)
            {
                kind++;
            }//增加水果种类
            hash[fruits[right]]++;//进窗口
            while(kind>2)
            {
               hash[fruits[left]]--;//出窗口
              if(hash[fruits[left]]==0)
               {
                kind--;
               }//更新水果种类
               left++;//更新left
            }
            nums=max(nums,right-left+1);//更新水果个数
        }
        return nums;

        
    }
};

小结：

本篇关于滑动窗口进阶题型的讲解就暂告一段落，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！

 

 

 

  

原文地址：https://blog.csdn.net/2303_81060385/article/details/143980832

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！