1004. 最大连续1的个数 III

1004. 最大连续1的个数 III

给定一个二进制数组 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。

---

——

---

C代码：

int longestOnes(int* nums, int numsSize, int k){
    int cnt = 0;
    int max = 0;
    int j = 0;
    for (int i = 0; i < numsSize; ++i) { // 遍历元素
        if (nums[i] == 0) {
            ++cnt;
        }
        while (cnt > k) {
            if (nums[j] == 0) {  // 改变循环的条件
                --cnt;
            }
            ++j;  // 满足条件就右移，收缩窗口
        }
        max = fmax(max, i - j + 1);
    }
    return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

Java代码1（最佳）：滑动窗口（用于求 连续问题）

滑动窗口有两个控制，外层for控制延伸，内层while控制收缩

class Solution {
    public int longestOnes(int[] nums, int k) {
        int l = 0;
        int cnt = 0;
        int ans = 0;
        for (int r = 0; r < nums.length; ++r) {  // 控制延伸
           if (nums[r] == 0) {
               ++cnt;
           }
            while (cnt > k) {  // 控制搜索：cnt > k 说明滑动窗口该收缩左边
                if (nums[l] == 0) {
                    --cnt;
                }
                ++l;
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

Java代码2：二分查找

---