如何高效检测环形数组中是否存在连续5个及以上的1？

问题场景 #

给定环形数组（首尾相连），需要判断其中是否存在连续5个及以上的1：

• 示例1：数组[1,1,1,0,0,1,1,1]，首尾的1连起来形成6个连续1，预期返回True
• 示例2：数组[0,1,0,1,1,0,1,1]，虽然总共有5个1，但没有连续的5个，预期返回False

原有方案问题 #

之前尝试的伪代码逻辑混乱，多次遍历数组且存在错误：

Populate the array.
Copy the array into a queue.
Go through the array again.
If the first element is 0, enqueue(dequeue()) until a 1 is found.
If it is 1, enqueue(dequeue) until a 0 is found.
//Now any series of 1 should not be wrapped around
Go through the array a third time, keeping a tally of 1 and a tally of 0.
If the array starts on 1 and 0 is found before 5 1s, return false.
If the array starts on 0 and a 1 is found before a consecutive group of 3 0s, return false
Return true if a series of 5 1s is found.
Return true if a series of 3 Os is found AND there are not more Os in the array.

高效解法（O(n)时间 + O(1)空间） #

核心思路：利用环形数组的特性，分别统计前缀连续1的数量、后缀连续1的数量，以及数组中间部分的最长连续1长度，最终判断这三者中的最大值（包括前缀+后缀的和）是否≥5。

具体步骤：

1. 提前剪枝：先遍历数组统计总1的数量total_ones，如果total_ones <5，直接返回False（连5个1都没有，不可能存在连续5个）
2. 全1情况：如果total_ones等于数组长度，直接返回True（所有元素都是1，必然满足条件）
3. 统计前缀连续1：从数组开头开始，连续计数1的个数，直到遇到第一个0为止，得到prefix_ones
4. 统计后缀连续1：从数组末尾开始，连续计数1的个数，直到遇到第一个0为止，得到suffix_ones
5. 统计中间最长连续1：遍历数组中间部分（去掉前缀和后缀的1），记录连续1的最大长度middle_max
6. 最终判断：计算最大连续1长度max_length = max(middle_max, prefix_ones + suffix_ones)，如果max_length ≥5则返回True，否则返回False

示例验证 #

• 对于数组[1,1,1,0,0,1,1,1]：
  prefix_ones=3，suffix_ones=3，middle_max=0，max_length=3+3=6≥5，返回True
• 对于数组[0,1,0,1,1,0,1,1]：
  prefix_ones=0，suffix_ones=2，middle_max=2，max_length=2<5，返回False
• 对于数组[1,1,1,0,1,1]：
  prefix_ones=3，suffix_ones=2，max_length=3+2=5≥5，返回True

内容的提问来源于stack exchange，提问作者Ben Alan