在做题中学习(45):最大连续1的个数III

2024-01-08 18:49:20

1004. 最大连续1的个数 III - 力扣(LeetCode)

解法:同向双指针————“滑动窗口”

思路:因为要返回数组中连续的数,就相当于一个子数组,而要的是一个可以翻转?<=? k个0的子数组使它可以变为全1的子数组,那就可以把问题转为:找出一个最大的子数组,它里面有<=k个0.

因此一定要定义一个计数器记录0的个数。

通过上图,可以看到当right进窗口到此位置时,子数组中0的个数 > k ,所以需要通过left出窗口来维持0的数量

1.left = 0,right = 0

2.进窗口————1就略过,0就计数器++

3.判断————0的个数>k

4.出窗口+再次判断————0就略过,1就left++

5.更新数据————选出更大的len

class Solution 
{
public:
    int longestOnes(vector<int>& nums, int k) 
    {
        int zcount = 0,len = 0;
        int z = 0;
        for(int left = 0,right = 0;right<nums.size();)
        {
            //1.进窗口
            if(nums[right]==0)
            {
                zcount++;
            }
            //2.判断
            while(zcount>k)
            {
                //3.出窗口
                if(nums[left]==1)
                {
                    left++;
                }
                else
                {
                    zcount--;
                    left++;
                }
            }
            //4.更新数据
            len = max(len,right - left + 1);
            right++;
        }
        return len;
    }
};

文章来源:https://blog.csdn.net/yiren_liusong/article/details/135463103
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。