Max Consecutive Ones
你会得到一个数组 nums，其中每个值都是 0 或 1。连续段是指一串彼此相邻的 1，中间没有 0。返回最长连续段的长度；如果数组中没有 1，则返回 0。
函数
- numsinteger-array
- 一个由 0 和 1 组成的数组
- 返回值integer
- 最长连续 1 的长度
约束条件
1 ≤ nums.length ≤ 2 × 104- 每个
nums[i]都是0或1。
示例
- 输入
- nums = [1, 1, 0, 1, 1, 1, 0, 1]
- 输出
- 3
- 解释
- 1 的连续段有 3 段：索引
0到1（长度为 2），索引3到5（长度为 3），以及单独的索引7（长度为 1）。最长的长度为3。
- 输入
- nums = [0, 1, 0, 1, 1]
- 输出
- 2
- 解释
- 索引
1处的单个 1 不如索引3和4处的一对，因此答案是2。
- 输入
- nums = [0, 0, 0]
- 输出
- 0
- 解释
- 任何地方都没有 1，所以没有连续段，答案是
0。
进阶
如果你最多可以把 k 个 0 翻转为 1，最长连续段可以有多长？你还能在一次遍历中找到它吗？
提示
逐个打开提示，每个都会多透露一点。
出现
0时，一串连续的1就结束了。你需要记住已经遍历过的值中的哪些信息？只有以当前索引结尾的连续段长度才重要。遇到 1 时，长度加 1；遇到 0 时，长度重置为 0。
用两个数字遍历数组一次：当前连续段的长度和目前为止的最长长度。每遇到一个 1，就增加当前连续段的长度，并将它与最长长度比较；每遇到一个 0，就重置当前连续段的长度。
题解
一旦出现 0，连续段就会结束，因此在每个索引处，你只需要知道以该位置结尾的连续段长度。用一个计数器，在遇到 1 时递增，遇到 0 时重置，就能通过一次遍历找到最长的连续段。
从每个索引开始向前计数
结果正确，但无法在最大的测试中运行完毕
思路
把每个索引都作为起点，向前遍历，直到遇到非 1 的值；步数就是从该位置开始的连续 1 的长度。最长的连续段一定从其中一个索引开始，所以最大计数就是答案。
这些遍历会相互重叠。对于一个长度为 n、元素全为 1 的数组，需要约 n² / 2 步；当 n = 2 × 10^4 时，需要 2 × 10^8 步。
算法
- 将
best = 0。 - 对于每个索引
start，将length = 0。 - 当
start + length在数组内，并且nums[start + length]是1时，将length加 1。 - 保留
best和length中较大的值。 - 返回
best。
def findMaxConsecutiveOnes(nums):
n = len(nums)
best = 0
for start in range(n):
length = 0
while start + length < n and nums[start + length] == 1:
length += 1
best = max(best, length)
return best单次遍历并计数
思路
让 current 表示以你当前所在索引结尾的连续 1 的长度。遇到 1 时，这段连续序列的长度加 1；遇到 0 时，这段序列结束，因此 current 变为 0。每段连续序列都在其最后一个索引处计数，此时 current 等于它的完整长度，因此 current 达到的最大值就是答案。
对于 [1, 1, 0, 1, 1, 1, 0, 1]，current 的值依次为 1、2、0、1、2、3、0、1，其中最大值是 3。
算法
- 将
best = 0和current = 0设为初始值。 - 对于
nums中的每个值：如果它是1，就给current加 1，并保留best和current中较大的值。 - 如果它是
0，就将current = 0。 - 返回
best。
def findMaxConsecutiveOnes(nums):
best = 0
current = 0
for x in nums:
if x == 1:
current += 1
best = max(best, current)
else:
# A 0 breaks the run.
current = 0
return best
易错点和边界情况
- 只有遇到
0时才更新best。如果一段连续序列一直延续到末尾，例如[0, 1, 1]，就永远不会记录这段序列。每遇到一个 1 后都更新，或者在循环后再比较一次。 - 遇到
0时没有重置current。不同的连续序列会累加，因此[1, 1, 0, 1, 1]会返回4。 - 将
best的初始值设为1或nums[0]。对于[0, 0, 0]，必须返回0。 - 在 Lua 和 R 中，数组从 1 开始索引，因此向前遍历时如果使用
< n而不是≤ n作为边界，就永远不会读取最后一个值，所以[0, 1]会返回0。
常见问题3
Max Consecutive Ones 的时间复杂度是多少？
一次遍历的解法运行时间为 O(n)，因为它只读取每个值一次，并且只使用 O(1) 的额外空间：一个计数器记录当前连续段的长度，另一个记录最长连续段的长度。在每个索引处都重新开始计数，对于全是 1 的数组，这样做需要 O(n²) 的时间。
为什么计数器会重置为 0，而不是 1？
计数器保存以当前位置结束的连续段的长度。当该位置的值为 0 时，没有以此处结束的连续 1 段，因此长度为 0。下一个 1 会将长度增加到 1，也就是新连续段的长度。
“最大连续 1 的个数”是滑动窗口问题吗？
你可以把它看作一个窗口：窗口保存当前运行的内容，它的右边缘会随着每个值移动，而 0 会让左边缘越过它。窗口不会一步步缩小，因此一个计数器就能代替两个边缘。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def findMaxConsecutiveOnes(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [1, 1, 0, 1, 1, 1, 0, 1]
预期输出
3