最大连续1的个数

发表于
本文字数： 2k 阅读时长 ≈ 2 分钟

LeetCode每日一题，1004. Max Consecutive Ones II

先看题目描述

yfYZuQ.png

给定一个数组 A 和一个整数 K，A 中只含 0 和 1，我们可以将 A 中的 K 个 0 替换为 1，问 A 中最长的连续的 1 的长度是多少

算法和思路

滑动窗口

第一反应就是对这题用滑动窗口来做，主要对滑动窗口执行两种操作，滑动和扩张，当窗口内的 0 的个数不超过 K 时，则将滑动窗口扩张；一旦窗口内 0 的个数超过 K，则移动滑动窗口，最后返回滑动窗口的大小即可

二分查找

这个方法是没想到的，看题解才知道可以用二分法做

先对问题进行转化，将问题转化为：对于任意的右端点 right，希望找到最小的左端点 left，使得 [left，right] 包含的 0 的个数不超过 K。只要我们枚举所有可能的右端点，将得到的区间长度取最大值，即可得到答案

要想快速判断一个区间内 0 的个数，我们可以考虑将数组 A 中的 0 变成 1，1 变成 0。此时，我们对数组 A 求出前缀和，记为数组 P，那么 [left，right] 中包含不超过 K 个 1，当且仅当 P[right] - P[left - 1] <= K

P[right] - P[left - 1] <= K 等价于 P[left - 1] >= P[right] - K

也就是说，我们需要找到最小的满足上式的 left，由于数组 A 中仅包含 0 和 1，因此前缀和数组是一个单调递增的数组，我们就可以使用二分查找法来得到 left

算法源码

滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int longestOnes(int[] A, int K) {
        int len = A.length;
        int cnt = 0;
        int left = 0;
        int right = 0;
        while (right < len) {
            if (A[right] == 0) {
                cnt++;
            }
            right++;
            if (cnt > K) {
                if (A[left] == 0) {
                    cnt--;
                }
                left++;
            }
        }
        return right - left;
    }
}

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int longestOnes(int[] A, int K) {
        int n = A.length;
        int[] P = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            P[i] = P[i - 1] + (1 - A[i - 1]);
        }

        int ans = 0;
        for (int right = 0; right < n; ++right) {
            int left = binarySearch(P, P[right + 1] - K);
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }

    public int binarySearch(int[] P, int target) {
        int low = 0, high = P.length - 1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (P[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}