TNotes.leetcode

Appearance

0485. 最大连续 1 的个数【简单】

0485. 最大连续 1 的个数【简单】 ​

1. 📝 题目描述 ​

给定一个二进制数组 nums， 计算其中最大连续 1 的个数。

示例 1：

txt
输入：nums = [1,1,0,1,1,1]
输出：3
解释：开头的两位和最后的三位都是连续 1，所以最大连续 1 的个数是 3.

示例 2：

txt
输入：nums = [1,0,1,1,0,1]
输出：2

提示：

  • 1 <= nums.length <= 10^5
  • nums[i] 不是 0 就是 1.

2. 🎯 s.1 - 一次遍历记录最大连续 1 ​

js
/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxConsecutiveOnes = function (nums) {
  let maxCount = 0
  let currentCount = 0

  for (let num of nums) {
    if (num === 1) {
      currentCount++
      maxCount = Math.max(maxCount, currentCount)
    } else {
      currentCount = 0
    }
  }

  return maxCount
}
  • 时间复杂度：O(n)，其中 n 是数组长度，需要遍历一次数组
  • 空间复杂度：O(1)，只使用了常数级别的额外空间

算法思路：

  • 遍历数组，使用 currentCount 记录当前连续 1 的个数
  • 遇到 1 则累加 currentCount 并更新 maxCount
  • 遇到 0 则重置 currentCount 为 0
  • 返回 maxCount 即为最大连续 1 的个数

3. 🎯 s.2 - 字符串切片 ​

js
/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxConsecutiveOnes = function (nums) {
  const newNums = nums
    .join('')
    .split('0')
    .filter((item) => item.length > 0) // ["11", "111"]
  let maxLen = 0
  for (let i = 0; i < newNums.length; i++) {
    let len = newNums[i].length
    maxLen = maxLen > len ? maxLen : len
  }
  return maxLen
}

// 其它写法：

// 使用 map 和展开运算符：
// var findMaxConsecutiveOnes = function (nums) {
//   const newNums = nums
//     .join('')
//     .split('0')
//     .filter((item) => item.length > 0) // ["11", "111"]
//   if (newNums.length === 0) return 0
//   return Math.max(...newNums.map((item) => item.length))
// }

// 使用正则：
// var findMaxConsecutiveOnes = function (nums) {
//   return Math.max(
//     ...nums
//       .join('')
//       .split(/0+/)
//       .map((item) => item.length)
//   )
// }
  • 时间复杂度：O(n)，其中 n 是数组长度，需要遍历转换后的字符串数组
  • 空间复杂度：O(n)，需要额外空间存储转换后的字符串和分割后的数组

算法思路：

  • 将数组转为字符串，然后按 '0' 分割，得到所有连续 1 的子串
  • 过滤掉空字符串，遍历找出最长子串的长度
  • 这种方法利用了字符串操作简化了逻辑

4. 🎯 s.3 - 正则的"正向预查" ​

js
/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxConsecutiveOnes = function (nums) {
  // => [1, 1, 0, 1, 1, 1]
  nums.push(0) // 往 nums 的结尾推一个 0，以便后续做正则匹配，实现切片。
  const str = nums.join(''),
    reg = /(1+)(?=0+)/g
  const arr = str.match(reg) // => ['11', '111']
  return arr ? Math.max(...arr.map((item) => item.length)) : 0
}
  • 时间复杂度：O(n)，其中 n 是数组长度，正则匹配需要扫描整个字符串
  • 空间复杂度：O(n)，需要存储匹配结果数组

算法思路：

  • 在数组末尾添加 0，确保正则能匹配到最后的连续 1
  • 使用正则 /(1+)(?=0+)/g 匹配所有连续的 1（后面跟着 0 的连续的 1）
  • (?=0+) 是正向预查，确保 1 后面有 0，但不消费 0
  • 找出所有匹配结果中最长的长度

Discussions