Medium

题目描述

你有一个长度为 n 的二进制字符串，起初所有位都是 0，字符串下标从 1 开始。我们会逐一翻转这个二进制字符串的所有位（即，将它们从 0 变为 1）。

给你一个下标从 1 开始的整数数组 flips ，其中 flips[i] 表示在第 i 步中翻转位于下标 flips[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^4
  • flips 是范围 [1, n] 中整数的一个排列。

解题思路

解题思路

这道题的关键洞察是：在第 i 步后，如果字符串是前缀一致的，那么前 i 位都必须是 1，其余位都是 0。

换句话说，在第 i 步后要达到前缀一致，我们必须已经翻转了位置 1, 2, 3, …, i 的所有位。

核心观察

如果我们跟踪到目前为止翻转的所有位置中的最大值，那么：

  • 当执行完第 i 步时，如果 max_flipped == i，说明我们已经翻转了位置 1 到 i 的所有位
  • 这正是前缀一致的条件

算法流程

  1. 遍历 flips 数组，维护一个变量 max_pos 记录到目前为止翻转的最大位置
  2. 在第 i 步（从 1 开始计数）后，如果 max_pos == i，则计数器加 1
  3. 返回总的前缀一致次数

这个方法的时间复杂度是 O(n)，空间复杂度是 O(1)，是最优解。

示例分析：

  • flips = [3,2,4,1,5]
  • 步骤1：翻转位置3，max_pos=3，3≠1，不前缀一致
  • 步骤2：翻转位置2，max_pos=3，3≠2，不前缀一致
  • 步骤3：翻转位置4，max_pos=4，4≠3，不前缀一致
  • 步骤4：翻转位置1，max_pos=4，4=4，前缀一致！
  • 步骤5：翻转位置5，max_pos=5，5=5，前缀一致！

代码实现

class Solution {
public:
    int numTimesAllBlue(vector<int>& flips) {
        int count = 0;
        int max_pos = 0;
        
        for (int i = 0; i < flips.size(); i++) {
            max_pos = max(max_pos, flips[i]);
            if (max_pos == i + 1) {
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def numTimesAllBlue(self, flips: List[int]) -> int:
        count = 0
        max_pos = 0
        
        for i, flip in enumerate(flips):
            max_pos = max(max_pos, flip)
            if max_pos == i + 1:
                count += 1
        
        return count

public class Solution {
    public int NumTimesAllBlue(int[] flips) {
        int count = 0;
        int maxPos = 0;
        
        for (int i = 0; i < flips.Length; i++) {
            maxPos = Math.Max(maxPos, flips[i]);
            if (maxPos == i + 1) {
                count++;
            }
        }
        
        return count;
    }
}

var numTimesAllBlue = function(flips) {
    let count = 0;
    let maxFlipped = 0;
    
    for (let i = 0; i < flips.length; i++) {
        maxFlipped = Math.max(maxFlipped, flips[i]);
        if (maxFlipped === i + 1) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需遍历一次数组
空间复杂度O(1)只使用常数额外空间

相关题目