1004. Max Consecutive Ones III

, ,

Prefix Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int longestOnes(int[] nums, int k) {
        // nums: [0, 0]
        // [0, 0, 0]
        int[] prefixSums = new int[nums.length + 1];
        for (int i = 1; i < prefixSums.length; i++) {
            prefixSums[i] = prefixSums[i - 1] + (nums[i - 1] ^ 1);
        }

        int maxLength = 0;
        for (int right = 1; right < prefixSums.length; right++) {
            if (right + 1 < prefixSums.length && prefixSums[right] == prefixSums[right + 1]) {
                continue;
            }

            // 此时选择 right 为右端点，寻找大于等于 target 的最左侧端点
            int target = prefixSums[right] - k;
            int left = findLeftIndex(prefixSums, 0, right, target);
            maxLength = Math.max(maxLength, right - left);
        }

        return maxLength;
    }

    private int findLeftIndex(int[] prefixSums, int left, int right, int target) {
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (prefixSums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
}

Sliding Window

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int longestOnes(int[] nums, int k) {
        int maxLength = 0;

        int zeroCount = 0;
        int i = 0;
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] == 0) {
                zeroCount++;
            }
            while (zeroCount > k) {
                if (nums[i++] == 0) {
                    zeroCount--;
                }
            }

            maxLength = Math.max(maxLength, j - i + 1);
        }

        return maxLength;
    }
}

References

1004. Max Consecutive Ones III