1004. 最大连续1的个数 III ●●

1004. 最大连续1的个数 III ●●

描述

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

示例

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

题解

1. 滑动窗口（双指针）

把「最多可以把 K 个 0 变成 1，求仅包含 1 的最长子数组的长度」
转换为
「找出一个最长的子数组，该子数组内最多允许有 K 个 0 」。

本题是求最大连续子区间，可以使用滑动窗口方法。滑动窗口的限制条件是：窗口内最多有 K 个 0。

代码思路：

1. 使用 left 和 right 两个指针，分别指向滑动窗口的左右边界。
2. right主动右移：right 指针每次移动一步。当 A[right] 为 0，说明滑动窗口内增加了一个 0；
3. left 被动右移：判断此时窗口内 0 的个数，如果超过了 K，则 left 指针被迫右移，直至窗口内的 0 的个数小于等于 K 为止。
4. 滑动窗口长度的最大值就是所求。

以 A= [1,1,1,0,0,0,1,1,1,1,0], K = 2 为例，下面的动图演示了滑动窗口的两个指针的移动情况。

• 时间复杂度：O(N)，因为每个元素只遍历了一次。
• 空间复杂度：O(1)，因为使用了常数个空间。

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int n = nums.size();
        int l = 0, ans = 0, zero = 0;
        for(int r = 0; r < n; ++r){
            if(nums[r] == 0) ++zero;		// 零个数 + 1
            while(zero > k){				// 零个数大于k时
                if(nums[l] == 0) --zero;	// 移动左指针
                ++l;
            }
            ans = max(ans, r - l + 1);		// 计算当前窗口的长度
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2. 前缀和 + 二分查找

枚举区间 左端点/右端点 ，然后找到其满足「出现 0 的次数不超过 k 次」的最远右端点/最远左端点。

为了快速判断 [ l, r ] 之间出现 0 的个数，我们需要用到前缀和。

假设 [l, r ] 的区间长度为 len，区间和为 tol，那么出现 0 的个数为 len - tol，再与 k 进行比较。

由于数组中不会出现负权值，因此前缀和数组具有「单调性」，那么必然满足「其中一段满足 len - tol <= k，另外一段不满足 len - tol <= k」。

因此，对于某个 确定的「左端点/右端点」 而言，以「其最远右端点/最远左端点」为分割点的前缀和数轴，具有「二段性」。可以通过二分来找分割点。

以下代码则具有确定的右端点，来查找从左往右第一个满足条件的左边界。

• 时间复杂度：$O(n\log n)$
• 空间复杂度：$O(n)$

class Solution {
public:
    bool check(vector<int>&sum, int l, int r, int k){   // 判断 l ~ r 区间内 0 的个数是否在 k 范围内
        int len = r - l + 1;
        return len - (sum[r+1] - sum[l]) <= k;
    }

    int longestOnes(vector<int>& nums, int k) {
        int n = nums.size(), ans = 0;
        if(n == 0) return 0;
        vector<int> sum(n+1, nums[0]);
        for(int i = 1; i <= n; ++i) sum[i] = sum[i-1] + nums[i-1];  // 统计前缀和，下标 i 以内的前缀和为 sum[i+1]
        for(int i = 0; i < n; ++i){             // 以 i 为右边界
            int l = 0, r = i;
            while(l < r){                       // 二分查找满足 以 i 为右边界，0 的个数小于等于 k 的 从左往右第一个左边界
                int mid = (l+r)>>1;
                if(check(sum, mid, i, k)){
                    r = mid;                    // 边界往左推
                }else{
                    l = mid + 1;                // 不满足，往右推
                }
            }
            if(check(sum, r, i, k)) ans = max(ans, i - r + 1);  // 再次检查一遍，计算区间长度
        }
        return ans;
    }
};
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

关于二分结束后再次 check 的说明：由于「二分」本质是找满足某个性质的分割点，通常我们的某个性质会是「非等值条件」，不一定会取得 =。

例如我们很熟悉的：从某个非递减数组中找目标值，找到返回下标，否则返回 -1。

当目标值不存在，「二分」找到的应该是数组内比目标值小或比目标值大的最接近的数。因此二分结束后先进行 check 再使用是一个好习惯。