算法笔记--最大连续1的个数Ⅲ

leetcode题目链接:1004. 最大连续1的个数 III

题目描述

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

思路

这里可以转换思路，让题意更加明确:即，求一个最大连续区间，要求该区间中的0的个数最多为k个
这样一来就变成了滑动窗口问题：
滑动窗口右侧right：

• 遇到1了，就记录当前窗口大小，并记录窗口最大值

• 遇到0了
  如果当前窗口0的个数不足k个（<K）则更新窗口中0的个数
  如果当前窗口0的个数以满足k个，则强制移动窗口左侧left，直到left“吐出”一个1

代码

class Solution {//转换问题看法:求一个连续最大区间，要求这个区间中0的个数最多为K个public int longestOnes(int[] nums, int k) {int len = nums.length; //数组长度int left=0;int right=0;int numOfZero = 0;//记录当前区间0的个数int maxLen = 0; //记录区间最大长度for(;right<len;right++){if(nums[right] == 0){//遇到0了if(numOfZero < k){//还可以变numOfZero++;maxLen = Math.max(maxLen,right-left+1);//记录最长区间}else{//k不够了,刚好numOfZero = k，这时需要left吐一个0出来while(left <= right){if(nums[left] == 0){left++;numOfZero--;if(nums[right] == 0)numOfZero++; //这里把left之前指向的0吐出去后，还要看新的right有没有指向0break;}else{left++;}}maxLen = Math.max(maxLen,right-left+1);//记录最长区间}}else{//遇到1了maxLen = Math.max(maxLen,right-left+1);//记录最长区间}}return maxLen;}
}