最大连续 1 的个数 III

#leetcode #2024/07/28 #算法/滑动窗口

目录

• 题目及理解
  • 原题不好理解，换种问法
• 解题思路
• 代码实现
  • 复杂度分析
• 错误记录

题目及理解

原题不好理解，换种问法

• 如果我可以改变最多 k 个 0，那么我能得到的最长的连续 1 序列有多长 ？
• 看题目是：最大连续 1 的个数

解题思路

1. 使用两个指针 left 和 right，初始都指向数组开头。
   1. 向右移动 right 指针，扩大窗口。
   2. 如果遇到 0，就将 k 减 1。
2. 当 k 小于 0 时，说明窗口内 0 的数量超过了允许的最大值，这时需要收缩窗口：
   • 移动 left 指针
   • 如果 left 指针经过的是 0，就将 k 加 1
3. 在每次迭代中更新最大窗口长度。

代码实现

/**
 * @param {number[]}  nums
 * @param {number} k  0 的个数
 * @return {number}
 */
var longestOnes = function (nums, k) {
  // 左指针
  let left = 0;
  // 右指针
  let right = 0;

  // 结果：最长的连续的 1 的个数
  let res = 0;

  // 向右移动 right 指针，扩大窗口
  for (; right < nums.length; right++) {
    // 如果遇到 0，就将 k 减 1
    // 如果当前数字是 0，就减少可用的 k
    if (nums[right] === 0) {
      k--;
    }

    // 如果 k 小于 0，需要移动左指针
    // 说明窗口内 0 的数量超过了允许的最大值，这时需要收缩窗口
    if (k < 0) {
      // 如果左指针指向的是 0，增加可用的 k
      if (nums[left] === 0) {
        k++;
      }
      left++;
    }

    // 在每次迭代中更新最大窗口长度
    res = Math.max(res, right - left + 1);
  }

  return res;
};

为什么是 right - left + 1，而不是 right - left ？

• 在数组中，索引是从 0 开始的。例如，如果 left = 0，right = 3，那么实际上包含了 4 个元素（索引 0, 1, 2, 3）

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。我们只遍历了一次数组。
• 空间复杂度：O(1)，我们只使用了常数额外空间

错误记录