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

难度: Medium

给你一个长度为 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.length
1 <= n <= 5 * 10⁴
flips 是范围 [1, n] 中所有整数构成的一个排列

Submission

运行时间: 48 ms

内存: 21.9 MB

class Solution:
    def numTimesAllBlue(self, flips: List[int]) -> int:
        # 想要保证第i次可以满足前缀一致，则在第i次时1到i-1的位置必须已经被翻过
        # 换言之第i次若可以满足，则第i次时的翻转位的大小一定小于等于i
        res = 0
        max = -1
        for i in range(len(flips)):
            if flips[i] > max:
                max = flips[i]

            if max <= i+1:
                res += 1

        return res

Explain

本题解的思路是通过维护一个最大翻转位置的变量来判断是否满足前缀一致的条件。遍历flips数组，每次更新最大翻转位置，如果当前最大翻转位置小于等于当前步数（i+1），则说明在当前步骤下，前缀一致的条件得到满足，因此结果计数加1。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def numTimesAllBlue(self, flips: List[int]) -> int:
        res = 0  # 初始化结果计数为0
        max = -1  # 初始化最大翻转位置为-1
        for i in range(len(flips)):
            if flips[i] > max:
                max = flips[i]  # 更新最大翻转位置

            if max <= i+1:
                res += 1  # 如果满足前缀一致条件，结果计数加1

        return res  # 返回最终结果

Explore

在本题中，前缀一致的条件意味着在步骤i（从0开始计数）结束时，前i+1个位置都已被翻转至少一次。这就要求在前i+1步中，最大翻转位置至少达到i+1。如果最大翻转位置max小于等于i+1，意味着在步骤i之前的翻转已经覆盖了前i+1个位置，因此这些位置的状态是一致的。这样的检查保证了我们可以正确地数出满足前缀一致条件的步数。

在算法中，我们关注的是确保所有位置至少被翻转一次，因此最关键的信息是已经遇到的最大翻转位置。只检查当前翻转位置是否大于已知的最大翻转位置是足够的，因为我们想知道翻转操作是否扩展了已翻转的范围。翻转顺序不会影响判断结果，因为无论翻转的顺序如何，只要每个位置最终都被翻转，就能满足前缀一致的条件。

如果数组flips中存在重复数字，即某个位置被翻转多次，这并不会影响算法的基本行为或最终的前缀一致次数计算。这是因为算法只关心最大翻转位置是否达到或超过当前步骤数。重复翻转同一个位置不会使最大翻转位置有新的增长，因此不会影响结果计数的逻辑。

变量max初始化为-1是为了正确处理第一次翻转操作前的情况。由于数组索引从0开始，如果max初始化为0，那么在处理第一个元素之前，算法会错误地认为位置0已经被覆盖，这可能导致错误的计数。初始化为-1确保在第一个翻转发生前，没有任何位置被认为已翻转，从而保证计数的正确性。