1004. Max Consecutive Ones III

O(n) time O(1) space
sliding window
find the longest subarray with at most K zeros

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

class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int l = 0, n = A.size();
        for (int r = 0; r < n; ++r) {
            if (A[r] == 0) --K;
            if (K < 0 && A[l++] == 0) ++K; // 必须把K < 0放前头，K < 0说明0太多了，需要剔除一些（因为1是不会对K变小做贡献的）直到把K变成非负为止（或者r指针到头了）
        }
        return n - l;
    }
};

O(nlogn) time O(1) space
bisection + sliding window

class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int n = A.size();
        int lo = 0, hi = n;
        while (lo <= hi) {
            int m = lo + (hi - lo) / 2;
            auto ret = isValid(A, K, m);//cout<<"m = "<<m<<", ret = "<<ret<<endl;
            if (ret) {
                lo = m + 1;
            } else {
                hi = m - 1;
            }
        }
        return lo - 1;
    }

    bool isValid(const vector<int> &A, int K, int m) {
        for (int l = 0, r = 0, cnt = 0; r < A.size(); ++r) {
            if (A[r] == 0) {
                ++cnt;
            }
            if (cnt <= K && r - l + 1 == m) return true;
            while (l < r && cnt > K) {
                if (A[l++] == 0) --cnt;
            }
        }
        return m == 0;
    }
};