题目描述
Given a binary array nums and an integer k, return the maximum number of consecutive 1’s in the array if you can flip at most k 0’s.
Example 1:
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Example 2:
Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Constraints:
- 1 <= nums.length <= 10^5
- nums[i] is either 0 or 1.
- 0 <= k <= nums.length
题目分析
首先，我们将问题进行一个转换，即求含有不超过k个0的子数组的最大长度；首先想到的是利用prefix sums，对于每一个可能的长度，利用prefix sums在O(1)时间内求出0的个数，判断是否满足条件
按照这个思路，我们可以写出如下代码:
// TLE
func longestOnes(nums []int, k int) int {
// m[i] 表示到nums[i-1] 为止， 总计有多少个0
m := make(map[int]int, len(nums)+1)
zeroNum := 0
for k, v := range nums {
if v == 0 {
zeroNum++
}
m[k+1] = zeroNum
}
// 从最大长度开始，查找满足条件的第一个子数组长度，即为所求
for length := len(nums); length >= k; length-- {
for start := 0; start+length-1 < len(nums); start++ {
if m[start+length]-m[start] <= k {
return length
}
}
}
return k
}
但是这个方法仍然属于一个O(N^2)的复杂度的方案，不出所料TLE了；所以我们需要进行优化；
思考一阵后，发现可以采用sliding window的方式来求解，方法如下:
- 维护2个pointer: left, right; 初始均指向0; 再维护一个统计0数量的变量 zeroNums
- 如果right指向的当前字符为0，则zeroNums加1;
- 此时进行如下判断:
- 如果zeroNums小于等于指定的k，则更新最终结果ans
- 如果此时zeroNums已经超出k，则不断右移left，直至zeroNums小于等于k
- right右移一位；重复上诉判断过程
按照上诉方法，代码如下:
// AC 56ms
func longestOnesV2(nums []int, k int) int {
left, right := 0, 0
ans := k
zeroNum := 0
for {
if right >= len(nums) {
break
}
if nums[right] == 0 {
zeroNum++
}
if zeroNum <= k {
// 更新ans
ans = max(ans, right-left+1)
} else {
// 滑动左侧位置，确保zeroNums始终满足条件
for {
if left >= right || zeroNum <= k {
break
}
if nums[left] == 0 {
zeroNum--
}
left++
}
}
// 窗口右侧右移
right++
}
return ans
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}
示例代码
在提交AC后，发现评论区还有更简洁优雅的代码，也是利用sliding window思想，但是更为高效简洁
与提交AC的代码相比， 这段代码主要的差别在于left右移只移动一位，最后结果改为由 right - left 得出;
初看这段代码，似乎无法得出正确的解，因为循环退出的条件永远是 right == len(nums) - 1； 而我们知道，符合条件的子数组并不一定是以 right-1结尾的， 很可能在中间某一段；所以，这段代码能AC的解释就是它计算的只有符合条件的子数组最大长度，最后的left, right指向的这个子数组并不一定就是目标子数组;
现在我们来看下为什么这段代码能得出符合条件的子数组最大长度。
func longestOnesV3(nums []int, k int) int {
var left, right, zeros int
for right < len(nums) {
if nums[right] == 0 {
zeros++
}
// 如果zeros超出k，进行滑动操作
// 说明此时right指向的位置一定为0
if zeros > k {
// 原left位置如果值为0，则zeros减1
if nums[left] == 0 {
zeros--
}
// left向右滑动一位
left++
}
// right右移
right++
}
// 这里的滑动，可以理解为将k个0变换为1之后，整体进行右移；
// 以此在新的位置下探测是否能扩展window；如果在新的位置下能继续扩展，说明符合条件的长度可以进一步增加
return right - left
}