LeetCode 1004. Max Consecutive Ones III

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int n = A.size(), left = 0, right = 0, ans = 0;
        vector<int> P(n + 1);
        for (int i = 1; i <= n; ++i)
            P[i] = P[i - 1] + (1 - A[i - 1]);
        while (right++ < n) {
            left = lower_bound(P.begin(), P.end(), P[right] - K) - P.begin();
            ans = max(ans, right - left);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int n = A.size(), left = 0, right = 0, cnt = 0, ans = 0;
        while (right < n) {
            if (A[right++] == 0)
                ++cnt;
            while (cnt > K)
                if (A[left++] == 0)
                    --cnt;
            ans = max(ans, right - left);
        }
        return ans;
    }
};