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

约 3 分钟
文章信息 7 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 微软
标签
数组

题目描述

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

image-20260928224540062

image-20260928224540063

题意分析

二进制串最初全为 0，位置编号为 $1$ 到 $n$。flips 是这些编号的一个排列，每一步将指定位置从 0 变成 1。完成第 $t$ 步后，若恰好前 $t$ 位为 1、其余位为 0，就计数一次。

解法：前缀最大编号计数

核心思路

[!blue]

处理完代码下标 i 后，因为编号不会重复，已经有且只有 i + 1 个位置变成 1。维护这些位置的最大编号 maxPos，就能判断它们是否恰好填满前缀。

如果前缀一致，变成 1 的位置必然是 $1$ 到 $i+1$，最大编号自然为 i + 1。反过来，若 maxPos == i + 1，这 i + 1 个不同位置全部落在只有 i + 1 个位置的区间内，只能把它完全填满；更后面没有已翻转位置，也就全部仍为 0。因此这一等式既是必要条件，也是充分条件。

若 maxPos > i + 1，至少有一个 1 落在目标前缀之外，前缀内必然还缺一个位置；maxPos < i + 1 则不可能容纳这么多不同位置。于是每步只需先更新最大编号，再判断一次等式，无需保存或扫描整个二进制串。

解题步骤

  • 初始化 maxPos = 0、answer = 0。
  • 按原顺序扫描 flips，将本次编号并入 maxPos。
  • 比较 maxPos 与 i + 1，相等则将答案加一。
  • 全部操作结束后返回答案。

代码实现

class Solution {
    public int numTimesAllBlue(int[] flips) {
        int maxPos = 0;
        int answer = 0;

        for (int i = 0; i < flips.length; i++) {

            // 先包含本步新编号，再判断是否填满前缀。
            maxPos = Math.max(maxPos, flips[i]);

            // 排列保证已打开 i 加一个位置，数量追平最大编号则没有空洞。
            if (maxPos == i + 1) {
                answer++;
            }
        }

        return answer;
    }
}

func numTimesAllBlue(flips []int) int {
    maxPos := 0
    answer := 0

    for i, pos := range flips {

        // 先包含本步新编号，再判断是否填满前缀。
        if pos > maxPos {
            maxPos = pos
        }

        // 排列保证已打开 i 加一个位置，数量追平最大编号则没有空洞。
        if maxPos == i+1 {
            answer++
        }
    }

    return answer
}

复杂度分析

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(1)$。

关键点总结

[!green]

  • 数量来自排列的无重复保证，不能推广到反复翻同一位置的输入。
  • 全亮也属于合法前缀。
  • 代码下标从 0 开始，位置编号从 1 开始，因此已完成的操作数是 i + 1；初始全零状态不计数。

易错点总结

[!yellow]

  • 用当前 flips[i] 而不是历史最大值，不能判断前面是否还有空洞。
  • 先判断后更新，会忽略本步刚亮起的位置。
  • 排序 flips 会改变操作顺序，得到的已不是题目要求统计的过程。

相似题目

题目 难度 关联与区别
769. 最多能完成排序的块 中等 同样利用排列前缀的最大值判断是否已包含完整连续前缀，已翻数量等于最大位置时前缀一致。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/98843001
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！