Max Consecutive One III

medium 原题链接：https://leetcode.com/problems/max-consecutive-ones-iii/

Max consecutive one III

原题链接

描述

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.

例子

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.

解法

Slide Window

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

slide window 的目的在于在窗口内做特定的操作，以降低嵌套深度。

在此，题目可以理解为：找到最长为K个零的最长子数组。

那么：

For each A[j], try to find the longest subarray. If A[i] ~ A[j] has zeros <= K, we continue to increment j. If A[i] ~ A[j] has zeros > K, we increment i (as well as j).