1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int longestOnes(int[] nums, int k) {
        int left = 0, right, zeroCount = 0;
        for (right = 0; right < nums.length; right++) {
            if (nums[right] == 0)
                zeroCount += 1;
            if (zeroCount > k && nums[left++] == 0) {
                zeroCount -= 1;
            }
        }
        return right - left;
    }
}

这道题的思路关键在于不缩window. 我们让left和right都先等于0, 然后开始移动right. 到达某个时刻, 我们发现0的个数大于k, 也就是当计算上right此时指向的0后, 发现count大于k. 此时我们知道left在等于0处, right最远可以到现在的位置. 此时我们开始移动这个构造好的window. 并且实时记录window中0的个数. 可能会有个时刻我们发现window中的count不再大于k而是等于k了. 此时left就不必动了, 只是移动right就行了. 这样到right出界, 我们得到的window size就是最大的. 直接right - left即可. 为什么不包括right这个位置? 因为我们是在遇到count大于k的时候才会停止扩张window. 此时valid的长度就是window size - 1.

时间复杂度: O(n)
空间复杂度: O(1)