LeetCode 487. 最大连续1的个数 II

Categories:

题目描述
思路分析
1. 解法一：滑动窗口（推荐）
2. 解法二：DP 记录上一个 0 前的连续 1
相似题目

题目描述

✅ 487. 最大连续1的个数 II

思路分析

解法一：滑动窗口（推荐）

核心思路：

窗口内允许最多一个 0。

右指针扩展窗口，若 0 的数量超过 1，则移动左指针收缩。

维护窗口最大长度即可。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)。

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int left = 0;
        int zeros = 0;
        int best = 0;

        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == 0) {
                zeros++;
            }

            while (zeros > 1) {
                if (nums[left] == 0) {
                    zeros--;
                }
                left++;
            }

            best = Math.max(best, right - left + 1);
        }

        return best;
    }
}

func findMaxConsecutiveOnes(nums []int) int {
	left := 0
	zeros := 0
	best := 0

	for right := 0; right < len(nums); right++ {
		if nums[right] == 0 {
			zeros++
		}

		for zeros > 1 {
			if nums[left] == 0 {
				zeros--
			}
			left++
		}

		if right-left+1 > best {
			best = right - left + 1
		}
	}

	return best
}

解法二：DP 记录上一个 0 前的连续 1

核心思路：

prev 记录上一个 0 前连续 1 的数量，curr 记录当前连续 1 的数量。

遇到 0 时，把 prev 更新为 curr，curr 置 0。

当前可获得的最长长度为 prev + 1 + curr。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)。

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int prev = 0;
        int curr = 0;
        int best = 0;

        for (int num : nums) {
            if (num == 1) {
                curr++;
            } else {
                prev = curr;
                curr = 0;
            }

            best = Math.max(best, prev + 1 + curr);
        }

        return Math.min(best, nums.length);
    }
}

func findMaxConsecutiveOnes(nums []int) int {
	prev := 0
	curr := 0
	best := 0

	for _, num := range nums {
		if num == 1 {
			curr++
		} else {
			prev = curr
			curr = 0
		}

		if prev+1+curr > best {
			best = prev + 1 + curr
		}
	}

	if best > len(nums) {
		return len(nums)
	}
	return best
}

相似题目

题目	难度	考察点
485. 最大连续1的个数	简单	滑动窗口
1004. 最大连续1的个数 III	中等	滑动窗口
1493. 删掉一个元素以后全为 1 的最长子数组	中等	双指针
424. 替换后的最长重复字符	中等	滑动窗口
209. 长度最小的子数组	中等	滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/20555284