Max Consecutive Ones III

1004. 最大连续1的个数III

分析

定义两个指针 i 和 j，表示滑动窗口的左右边界
使用变量 cnt 记录当前窗口中 0 的个数
遍历数组 nums ：
- 如果遇到 0，增加 cnt
- 当 cnt > k 时，说明当前窗口内翻转 0 的数量超出了限制，需要将左指针 j 向右移动，并且如果移除的元素是 0，更新 cnt
- 每次移动右指针 i 时，计算当前窗口的长度 res = max(res, i - j + 1)
遍历完成后，返回最大窗口长度 res

时间复杂度

总时间复杂度 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution
{
public:
    int longestOnes(vector<int>& nums, int k)
    {
        int res = 0;       // 最大连续 1 的长度
        int cnt = 0;       // 当前窗口内 0 的数量
        for (int i = 0, j = 0; i < nums.size(); ++i)
        {
            if (nums[i] == 0)
                ++cnt;    // 遇到 0，增加计数
            while (cnt > k)  // 如果翻转的 0 超过限制
            {
                if (nums[j] == 0)
                    --cnt; // 左指针移除 0，减少计数
                ++j;       // 缩小窗口
            }
            res = std::max(res, i - j + 1); // 更新最大长度
        }
        return res;
    }
};