LeetCode-1004:最大连续1的个数 III

举报
小小谢先生 发表于 2022/04/16 02:17:17 2022/04/16
【摘要】 题目描述: 给定一个由若干 0 和 1 组成的数组 A,我们最多可以将 K 个值从 0 变成 1 。 返回仅包含 1 的最长(连续)子数组的长度。   示例 1: 输入:A = [1,1,1,0,0,0,1,1,1,1,0], K = 2 输出:6 解释:  [1,1,1,0,...

题目描述:

给定一个由若干 0 和 1 组成的数组 A,我们最多可以将 K 个值从 0 变成 1 。

返回仅包含 1 的最长(连续)子数组的长度。

 

示例 1:

输入:A = [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:

输入:A = [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。

 

思路分析:

一看到最大两字,就先想到滑动窗口。然后再读题意,可知就是用滑动窗口解决。

我们可以理解为,滑动窗口内最多有K个0,求滑动窗口最大的长度。

接下来代码就简单啦!


      class Solution {
         public int longestOnes(int[] A, int K) {
             int count=0;//统计0的个数
             int left=0;//滑动窗口区间左端点
             int right=0;//滑动窗口区间右端点
             int res=0;//最终结果
             //滑动窗口表示的区间为[left,right),左闭右开
             while(right<A.length){
                 if(A[right++]==0){//窗口扩充一个元素,如果为0则count++;
                      count++;
                  }
                 while(count>K){//当窗口内0的个数超过k时候,开始收缩窗口
                     if(A[left++]==0){//如果刚滑出窗口的元素是0,则count--;
                          count--;
                      }
                  }
                 //此时count<=K,保存窗口的最大宽度
                  res=Math.max(res,right-left);
              }
             return res;
          }
      }
  
 

 

文章来源: blog.csdn.net,作者:小小谢先生,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/xiewenrui1996/article/details/113748250

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。