算法分享——《滑动窗口》-????《最大连续1的个数 III》

时间:2024-09-29 22:11:36

????题目描述:

给定一个二进制数组 nums 和一个整数 k,如果可以翻转最多 k0 ,则返回 数组中连续 1 的最大个数

示例 1:

输入:nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], K = 2
输出:6
解释:[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1]
粗体数字从 0 翻转到 1,最长的子数组长度为 6。

示例 2:

输入:nums = [0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1], K = 3
输出:10
解释:[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1]
粗体数字从 0 翻转到 1,最长的子数组长度为 10。

????代码实现:

class Solution 
{
public:
    int longestOnes(vector<int>& nums, int k) 
    {
        int sumzero = 0;
        int len = 0;
        for(int left = 0, right = 0; right <nums.size(); ++right)
        {
            if(nums[right] == 0) ++sumzero;
            while(sumzero > k)
                if(nums[left++] == 0) --sumzero;
            len = max(len, right - left + 1);
        }
        return len;
    }
};

????代码解析:

我们可以对问题进行深入理解理解,首先题目所讲的是K,它是一个最大的范围,我们可以翻转1次也可以翻转K - 1次也都可以。

如果用暴力来解决这道题的话,就需要一个一个的将0转换成1,这样子的话代码实现过于复杂了。
我们可以简化一下题目描述,我们其实想找到的是一个子数组,这一个子数组中有K个0或K个以下数的0变成1后能满足最大的长度
所以我们只需要通过left指针和right指针遍历这个数组,统计0的个数,然后判断是否超过了K,如果超过了K就记录这个长度,然后再让left++让right回来继续遍历,然后一个一个的判断。这其实也是一种暴力解法,但是好在我们把问题简化了。

现在我们可以来尝试模拟一遍:在这里插入图片描述

如果此时我们对0的个数进行统计之后,结果大于k了:
image-20240914232422311

我们left++然后再让right回到left这里:
image-20240914232517290

那当我们的right还是会经过那两个0,我们又要再让left++,right也又要回来
image-20240914232623862

image-20240914232635094

这不是上面那个《无重复字符的最长子串》和《长度最小的子数组》结合起来后的题目嘛?
当我们的0的个数大于2时,我们就没必要再让right回来了,只要让left一直向右移,遇到0就让统计0的个数的变量减一,知道正好等于就让left停下来,然后再进行判断。这不就是滑动窗口嘛。

image-20240914234300434

image-20240914234905661