最大连续1的个数 III

题目:

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

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

解题思路


重点:

题意转换。把「最多可以把 K 个 0 变成 1,求仅包含 1 的最长子数组的长度」转换为 「找出一个最长的子数组,该子数组内最多允许有 K 个 0 」。
经过上面的题意转换,我们可知本题是求最大连续子区间,可以使用滑动窗口方法。滑动窗口的限制条件是:窗口内最多有 K 个 0。

可以使用我多次分享的滑动窗口模板解决,模板在代码之后。

代码思路:

使用 left 和 right 两个指针,分别指向滑动窗口的左右边界。
right 主动右移:right 指针每次移动一步。当 A[right] 为 0,说明滑动窗口内增加了一个 0;
left 被动右移:判断此时窗口内 0 的个数,如果超过了 K,则 left 指针被迫右移,直至窗口内的 0 的个数小于等于 K 为止。
滑动窗口长度的最大值就是所求。
示例
以 A= [1,1,1,0,0,0,1,1,1,1,0], K = 2 为例,下面的动图演示了滑动窗口的两个指针的移动情况。

代码

package main

import "fmt"

func slide_windows(num []int, K int) (ans int) {
	var left, rsum, lsum int
	for right, v := range num {
		rsum += 1 - v
		if lsum < rsum-K {
			lsum += 1 - num[left]
			left++
		}
		sss := right - left + 1
		ans = max(ans, sss)
	}
	return
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func main() {
	A := []int{1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0}
	K := 2
	res := slide_windows(A, K)
	fmt.Println(res)
}

  

small_lei_it 技术无止境,追求更高。
原文地址:https://www.cnblogs.com/smallleiit/p/14419477.html