旺崽的博客

要么天赋异禀，要么天道酬勤

0%

LeetCode 1004 最大连续1的个数 III

发表于 分类于 Valine：

题目链接

给定一个由若干 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。

双指针~
这题和 LeetCode 424 替换后的最长重复字符 方法一模一样，就是利用双指针的思想找最大区间，AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestOnes(vector<int> &A, int K) {
        int l = 0, r = 0, n = A.size(), num0 = 0, num1 = 0, mx = 0;
        while (r < n) {
            A[r] ? num1++ : num0++;
            mx = max(mx, num1);
            if (r - l + 1 - mx > K) {
                A[l] ? num1-- : num0--;
                l++;
            }
            r++;
        }
        return r - l;
    }
};