1004. Max Consecutive Ones III

 一刷 07/2022

Version #2 Sliding Window without comparing the max

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

答案有一个很神奇的解法就是每次不对比max，而是最后直接返回end - start

这个答案我一开始看感到匪夷所思

他的关键在于当k < 0的时候，每次increment i by 1，如果k还有余量，i就不动，这样window就在变大

所以它不是维护一个valid的window，而是用已知的最大window一直扫描，遇到invalid的时候就维持已知的window size不变(by incrementing i by 1 while j is incremented by 1)，而遇到valid的时候就让window自动扩大

Version #1 Sliding Window

Time O(N)

Space O(1)

Runtime: 3 ms, faster than 91.60% of Java online submissions for Max Consecutive Ones III.

Memory Usage: 72 MB, less than 21.31% of Java online submissions for Max Consecutive Ones III.

class Solution {

    public int longestOnes(int[] nums, int k) {

        // keep a sliding window that having at most k 0's

        int zeroCount = 0;

        int start = 0;

        int len = 0;

        for (int end = 0; end < nums.length; end++) {

            if (nums[end] == 0) {

                zeroCount++;

            }

            while (zeroCount > k) {

                if (nums[start] == 0) {

                    zeroCount--;

                }

                start++;

            }

            len = Math.max(len, end - start + 1);

        }

        return len;

    }

}