[LeetCode] 1004. Max Consecutive Ones III

[grandyang]

Given an array A of 0s and 1s, we may change up to K values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1s.

Example 1:

Input: A = [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: A = [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.

Note:

1. 1 <= A.length <= 20000
2. 0 <= K <= A.length
3. A[i] is 0 or 1

这道题是之前那道 Max Consecutive Ones II 的拓展，博主在之前的解法二中就预言了翻转k次的情况，果不其然，在五百多道题之后，该来的还是来了。不过不要紧，我们已经知道了该如何应对了，直接上滑动窗口 Sliding Window，用个变量 cnt 记录当前将0变为1的个数，在遍历数组的时候，若遇到了0，则 cnt 自增1。若此时 cnt 大于K了，说明该缩小窗口了，用个 while 循环，若左边界为0，移除之后，此时 cnt 应该自减1，left 自增1，每次用窗口大小更新结果 res 即可， 参见代码如下：

解法一：

class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int n = A.size(), left = 0, cnt = 0, res = 0;
        for (int i = 0; i < n; ++i) {
            if (A[i] == 0) ++cnt;
            while (cnt > K) {
                if (A[left] == 0) --cnt;
                ++left;
            }
            res = max(res, i - left + 1);
        }
        return res;
    }
};

我们也可以写的更简洁一些，不用 while 循环，但是还是用的滑动窗口的思路，其中i表示左边界，j为右边界。在遍历的时候，若遇到0，则K自减1，若K小于0了，且 A[i] 为0，则K自增1，且i自增1，最后返回窗口的大小即可，参见代码如下：

解法二：

class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int n = A.size(), i = 0, j = 0;
        for (; j < n; ++j) {
            if (A[j] == 0) --K;
            if (K < 0 && A[i++] == 0) ++K;
        }
        return j - i;
    }
};

Github 同步地址:

#1004

类似题目：

Number of Substrings Containing All Three Characters

Count Number of Nice Subarrays

Replace the Substring for Balanced String

Binary Subarrays With Sum

Fruit Into Baskets

Shortest Subarray with Sum at Least K

Minimum Size Subarray Sum

Longest Substring with At Most Two Distinct Characters

Longest Substring with At Least K Repeating Characters

Longest Substring with At Most K Distinct Characters

Max Consecutive Ones II

Max Consecutive Ones

参考资料：

https://leetcode.com/problems/max-consecutive-ones-iii/

https://leetcode.com/problems/max-consecutive-ones-iii/discuss/247564/JavaC%2B%2BPython-Sliding-Window

https://leetcode.com/problems/max-consecutive-ones-iii/discuss/247543/O(n)-Java-Solution-using-sliding-window

LeetCode All in One 题目讲解汇总(持续更新中...)