---

1375. 二进制字符串前缀一致的次数

• 标签：数组
• 难度：中等

题目链接

• 1375. 二进制字符串前缀一致的次数 - 力扣

题目大意

描述：给定一个长度为 $n$ 的二进制字符串 $s$，初始时所有位都是 '0'。另外给定一个长度为 $n$ 的排列 $flips$，其中 $flips[i]$ 表示第 $i$ 步操作翻转 $s$ 的第 $flips[i]$ 位（从 $1$ 开始索引）。

要求：返回在 $flips$ 的每一步操作之后，$s$ 的前缀（前 $1$ 到前 $n$ 位）中，有多少个时刻其所有前缀位置都是 '1'。

说明：

• $1 \le n \le 5 \times 10^4$。
• $flips$ 是 $[1, n]$ 的一个排列。

示例：

• 示例 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 。

解题思路

思路 1：维护最大翻转位置

1. 核心思想

前 $k$ 位前缀一致，意味着 $1 \sim k$ 全部是 '1'，而 $k+1 \sim n$ 全部是 `'0'$。

翻转过程中，维护当前已经翻转过的位置中的最大值 $max\_flipped$。当某一步操作后，$max\_flipped$ 恰好等于已经操作的次数 $i + 1$（$0$ 索引），说明之前的所有位置都已经被翻转过了，即前 $max\_flipped$ 位全部为 `'1'$。

2. 正确性证明

因为 $flips$ 是排列，每位只翻转一次。第 $i$ 步后共翻转了 $i+1$ 个位置。

如果当前最大翻转位置 $= i+1$，说明 $[1, i+1]$ 这些位置全部被翻转了（最大值和总数匹配），此时前缀是一致的。

反之，如果最大值 $> i+1$，说明有大于 $i+1$ 的位置被翻转了，那么前 $i+1$ 位中必然有缺失（因为总共只有 $i+1$ 次翻转）。

3. 举例说明

以 $flips = [3, 2, 4, 1, 5]$ 为例：

步骤	翻转位	翻转位置集合	最大值	计数	前缀一致？
1	3		3	1	否 (3≠1)
2	2		3	2	否 (3≠2)
3	4		4	3	否 (4≠3)
4	1		4	4	是 (4=4)
5	5		5	5	是 (5=5)

答案为 $2$。

4. 另一种理解方式

$max\_flipped$ 表示当前翻转过的最右边的位置。当 $max\_flipped$ 恰好等于已翻转次数时，意味着 $[1, max\_flipped]$ 全部被填满，恰好对应前缀一致。

思路 1：代码

class Solution:
    def numTimesAllBlue(self, flips: List[int]) -> int:
        ans = 0
        max_flipped = 0  # 当前翻转过的最大位置

        for i, pos in enumerate(flips):
            max_flipped = max(max_flipped, pos)
            # 如果最大翻转位置 == 已翻转次数，则前缀一致
            if max_flipped == i + 1:
                ans += 1

        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n)$，只需遍历一次 $flips$。
• 空间复杂度：$O(1)$，只使用了常数个变量。

---

思路 2：对比类似问题

本题与「0769. 最多能完成排序的块」的核心思想相似：

• 769 题：将 $[0, n-1]$ 的排列分段，使得每段排序后整体有序
• 本题：每次翻转后检查前缀是否全部为 '1'

两题的共同点是维护当前段（或已翻转位置）的最大值，判断是否满足某种完备条件。