难度: Medium
Submission
运行时间: 51 ms
内存: 16.4 MB
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
n = len(nums)
res = 1
left = 0
i = 0
while i < n:
if nums[i] == 1:
left += 1
i += 1
else:
right = i + 1
while right < n and nums[right] == 1:
right += 1
if right != i + 1:
res = max(res, right - i + left)
left = right - i - 1
i = right
else:
res = max(res, left + 1)
left = 0
i += 1
return max(res, left)
Explain
该题解使用滑动窗口的思路来解决问题。使用两个指针 left 和 right，left 指向当前连续 1 的起始位置，right 向右扩展窗口。当遇到 0 时，计算当前窗口的长度，更新结果 res，然后将 left 移动到 right 的位置，继续向右扩展窗口。最后返回 res 和 left 中的最大值，即为最长连续 1 的长度。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
n = len(nums)
res = 1
left = 0
i = 0
while i < n:
if nums[i] == 1:
# 扩展左边界
left += 1
i += 1
else:
# 遇到 0，扩展右边界
right = i + 1
while right < n and nums[right] == 1:
right += 1
if right != i + 1:
# 更新结果
res = max(res, right - i + left)
# 更新左边界
left = right - i - 1
i = right
else:
# 更新结果
res = max(res, left + 1)
# 重置左边界
left = 0
i += 1
# 返回结果与左边界的最大值
return max(res, left)
Explore
题解中的逻辑`遇到0，扩展右边界`确实主要描述了在遇到0时如何处理和更新结果，这是因为0的出现可能中断连续的1序列。如果数组中没有0，该算法的循环会依然遍历整个数组，但因为没有0，i指针会连续前进，left会一直增加直到数组末尾。此时，left将记录整个数组的长度（如果全为1的话），这也会在最后通过`max(res, left)`得到正确的最大连续1的个数，即整个数组的长度。
在题解中，`left = right - i - 1`这一步骤发生在找到一个0后，right指针尝试跳过这个0并继续向前找连续的1。这一步骤的目的是为了更新left计数器，以反映在当前0之后的新一段连续1的长度。`right - i - 1`是因为right现在指向的是新段连续1的结束位置的下一个位置，减去i（当前0的位置）再减去1得到的是从i+1位置开始到right位置之前的1的数量，即新一段连续1的长度。
算法最后返回`max(res, left)`的原因在于考虑到数组末尾可能存在一段连续的1，这段连续1直到数组结束都没有被更长的序列打断。在这种情况下，left将会持续增加直到数组末尾，而如果在遍历过程中没有更新更大的res值，left可能会是最大的连续1的数量。因此，使用`max(res, left)`确保无论数组是否以1结束，都能返回正确的最大值。
在题解中，left初始化为0是因为在算法开始时，还没有遇到任何1，因此连续1的计数应从0开始。当遇到第一个1时，left会增加1，正确记录连续1的数量。如果left初始化为1，那么即使数组开头不是1，left的计数也会错误地高估。因此，初始化为0是为了精确地根据实际遇到的1的数量进行计数。