LeetCode1004-最大连续1的个数III

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/max-consecutive-ones-iii/

中文链接：https://leetcode-cn.com/problems/max-consecutive-ones-iii/

题目详述

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。

返回仅包含 1 的最长（连续）子数组的长度。

示例 1：

1
2
3
4
5
输入：A = [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。

示例 2：

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

提示：

  1. 1 <= A.length <= 20000
  2. 0 <= K <= A.length
  3. A[i] 为 0 或 1

题目详解

滑动窗口，类似于 LeetCode424-替换后的最长重复字符。只不过本题只用统计最大连续 1 的个数，而不是统计最大连续字符的个数，相对而言要更简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LeetCode_01004 {

    public int longestOnes(int[] A, int K) {
        int res = 0;
        for (int l = 0, r = 0; r < A.length; ) {
            if (A[r++] == 0) {
                --K;
                while (K < 0) {
                    if (A[l++] == 0) {
                        ++K;
                    }
                }
            }
            res = Math.max(res, r - l);
        }
        return res;
    }
}

下面这种写法更简单，思路是一致的，区别在于它在达到一个最大窗口后，窗口不会缩小，也就是说有效窗口只可能变大或维持不变，不会缩小。

1
2
3
4
5
6
7
8
9
10
11
public class LeetCode_01004 {

    public int longestOnes(int[] A, int K) {
        int l = 0, r = 0;
        while (r < A.length) {
            if (A[r++] == 0) --K;
            if (K < 0 && A[l++] == 0) ++K;
        }
        return r - l;
    }
}