L46.【LeetCode题解】1004. 最大连续1的个数 III

zhangcoder

已于 2025-05-08 17:09:26 修改

阅读量899

点赞数 14

分类专栏： LeetCode题解 # 滑动窗口文章标签： leetcode 算法职场和发展开发语言 c++ 滑动窗口

于 2025-05-04 15:19:25 首次发布

本文链接：https://blog.csdn.net/2401_85828611/article/details/147649863

版权

LeetCode题解同时被 2 个专栏收录

55 篇文章

订阅专栏

滑动窗口

6 篇文章

订阅专栏

1.题目

https://leetcode.cn/problems/max-consecutive-ones-iii/description/

给定一个二进制数组 nums 和一个整数 k，假设最多可以翻转 k 个 0 ，则返回执行操作后 数组中连续 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。
提示：

1 <= nums.length <= 10^5
nums[i] 不是 0 就是 1
0 <= k <= nums.length

2.分析

容易想到的做法:统计二进制数组 nums 中0的个数为m,分类讨论:

1.当k $\leq$ m时,讨论m个0翻转1个、翻转2个、...、翻转k个的情况,针对每个情况求连续1的最大个数

2.当k $>$ m时,讨论m个0翻转1个、翻转2个、...、翻转m个的情况,针对每个情况求连续1的最大个数

比较麻烦,不建议使用

转化思路:设区间[left,right],如果该区间的所有0不超过k个(那就能将这些0变成1),则right-left+1就有可能成为连续1的最大个数

方法1:暴力解法

固定left,每次right从left出发向后枚举

以[1,1,1,0,0,0,1,1,1,1,1],k==2为例

sum[right]==1,不做任何处理

sum[right]==0,计数器zero++,发现zero<k,不做处理

sum[right]==0,计数器zero++,发现zero>k,left++

根据"固定left,每次right从left出发向后枚举"规则,暴力枚举需要重新让right从left处重新枚举

......(多次循环后)

之后让right走完全程即可

方法2:暴力解法的优化:滑动窗口

在方法1中,可以提高枚举的效率

......(多次循环后)

会发现画红框的这两种情况一模一样:

因此right不用回退!-->转化为同向双指针-->滑动窗口算法

步骤:

1.初始化窗口的两个端点:left=0,right=0,zero=0(zero为存储滑动窗口中0的个数)

2.进窗口:如果是1,不做任何处理;如果是0,zero++

3.判断zero是否大于k

zero>k,需要出窗口,即left++,(left++之前,如果nums[left]为1,不变动zero;如果nums[left]为0,不zero--;)直到zero $\leqslant$ k为止

zero<=k,不处理

4.记录可能的最大连续1的个数: count=max(count,right-left+1);

5.right<nums.size(),就重复步骤2和3

代码

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) 
    {
        int left=0,right=0,zero=0,count=0;//zero为滑动窗口中0个数
        for (;right<nums.size();right++)
        {
            if (nums[right])//nums[right]==1
            {
                //什么都不做
            }
            else//nums[right]==0
            {
                zero++;
                while(zero>k)
                {
                    if (nums[left]==0)
                         zero--;
                    left++;    
                }
            }
            count=max(count,right-left+1);
        }
        return count;
    }
};

提交结果

简化代码

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) 
    {
        int left=0,right=0,zero=0,count=0;//zero为滑动窗口中0个数
        for (;right<nums.size();right++)
        {
            if (!nums[right])
            {
                zero++;
                while(zero>k)
                {
                    if (nums[left]==0)
                         zero--;
                    left++;    
                }
            }
            count=max(count,right-left+1);
        }
        return count;
    }
};