LeetCode 题解工作台
二进制字符串前缀一致的次数
给你一个长度为 n 、下标从 1 开始的二进制字符串，所有位最开始都是 0 。我们会按步翻转该二进制字符串的所有位（即，将 0 变为 1 ）。 给你一个下标从 1 开始的整数数组 flips ，其中 flips[i] 表示对应下标 i 的位将会在第 i 步翻转。 二进制字符串 前缀一致 需满足：在第…
1
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·driven
答案摘要
我们可以遍历数组 ，记录当前遍历过的元素的最大值 ，若 等于当前遍历到的下标 ，则说明前 个元素都被翻转过了，即前缀一致，答案累加。 遍历结束后，返回答案即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·driven 题型思路
题目描述
给你一个长度为 n 、下标从 1 开始的二进制字符串，所有位最开始都是 0 。我们会按步翻转该二进制字符串的所有位（即，将 0 变为 1）。
给你一个下标从 1 开始的整数数组 flips ，其中 flips[i] 表示对应下标 i 的位将会在第 i 步翻转。
二进制字符串 前缀一致 需满足：在第 i 步之后，在 闭 区间 [1, i] 内的所有位都是 1 ，而其他位都是 0 。
返回二进制字符串在翻转过程中 前缀一致 的次数。
示例 1：
输入：flips = [3,2,4,1,5] 输出：2 解释：二进制字符串最开始是 "00000" 。 执行第 1 步：字符串变为 "00100" ，不属于前缀一致的情况。 执行第 2 步：字符串变为 "01100" ，不属于前缀一致的情况。 执行第 3 步：字符串变为 "01110" ，不属于前缀一致的情况。 执行第 4 步：字符串变为 "11110" ，属于前缀一致的情况。 执行第 5 步：字符串变为 "11111" ，属于前缀一致的情况。 在翻转过程中，前缀一致的次数为 2 ，所以返回 2 。
示例 2：
输入：flips = [4,1,2,3] 输出：1 解释：二进制字符串最开始是 "0000" 。 执行第 1 步：字符串变为 "0001" ，不属于前缀一致的情况。 执行第 2 步：字符串变为 "1001" ，不属于前缀一致的情况。 执行第 3 步：字符串变为 "1101" ，不属于前缀一致的情况。 执行第 4 步：字符串变为 "1111" ，属于前缀一致的情况。 在翻转过程中，前缀一致的次数为 1 ，所以返回 1 。
提示：
n == flips.length1 <= n <= 5 * 104flips是范围[1, n]中所有整数构成的一个排列
解题思路
方法一：直接遍历
我们可以遍历数组 ，记录当前遍历过的元素的最大值 ，若 等于当前遍历到的下标 ，则说明前 个元素都被翻转过了，即前缀一致，答案累加。
遍历结束后，返回答案即可。
时间复杂度 ，其中 为数组 的长度。空间复杂度 。
class Solution:
def numTimesAllBlue(self, flips: List[int]) -> int:
ans = mx = 0
for i, x in enumerate(flips, 1):
mx = max(mx, x)
ans += mx == i
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each flip is processed once and only simple max comparisons are performed. Space complexity is O(1) since no additional structures beyond counters are needed. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Tracking maximum flipped index indicates you understand the prefix alignment property.
- question_mark
Recognizing that step count equals maximum flipped index signals optimal use of array-driven checks.
- question_mark
Using a single pass with minimal storage demonstrates efficiency in handling the array pattern.
常见陷阱
外企场景- error
Checking all bits at each step instead of tracking max index can lead to O(n^2) time.
- error
Misinterpreting 1-indexed positions can cause off-by-one errors in alignment detection.
- error
Counting alignment at incorrect steps, ignoring that only max index equal to step matters.
进阶变体
外企场景- arrow_right_alt
Count prefix-aligned moments in a binary string where flips can include repeated indices.
- arrow_right_alt
Determine moments of suffix alignment where the trailing bits are all ones after each flip.
- arrow_right_alt
Compute prefix-aligned moments with a dynamic stream of flips arriving in real time.