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

2022-11-11 HGNULB 约 7 分钟

文章信息 7 个分类 1 个标签

分类

题目描述

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

题意分析

给定一个长度为 $n$ 的数组 flips，它是 $1$ 到 $n$ 的一个排列。初始有 $n$ 个编号为 $1..n$ 的灯泡全部关闭，第 $i$ 步（下标从 0 开始）把编号 flips[i] 的灯泡打开。每一步结束后，如果此刻「被打开的灯泡集合」恰好等于「编号前若干个连续灯泡」，就称这一步是前缀一致的，问一共有多少步前缀一致。

约束里最值钱的一条是 flips 是排列：每个编号只出现一次，永远不会重复打开，因此第 $i$ 步结束后被打开的灯泡数量恒等于 $i+1$。这把「集合是什么」这个复杂问题降级成了「集合的大小是多少」这个免费信息。

另一条信号是数据量 $n \le 10^5$，逐步维护一个字符串再逐位检查是否为 1...10...0 是 $O(n^2)$，会超时；必须找到能 $O(1)$ 判定的等价条件。

边界上要注意：题目问的是「有多少步之后」满足条件，最后一步一定满足（所有灯全开就是长度为 $n$ 的前缀），所以答案至少为 $1$；而 $n = 1$ 时答案就是 $1$。

解法：前缀最大编号计数

核心思路

最朴素的做法是真的维护一个长度为 $n$ 的布尔数组，每步打开一个位置后从头扫一遍，找到第一个 false 的位置，检查它后面是不是全 false。瓶颈很清楚：每步都要 $O(n)$ 的全量扫描，总代价 $O(n^2)$。

突破口是把「已开集合是一个前缀」翻译成一个可以增量维护的数值条件。设第 $i$ 步结束后已打开编号的最大值为 maxPos。已打开的灯泡全部落在 $[1, maxPos]$ 内，而这个区间总共有 maxPos 个位置。于是：已开集合恰好是前缀 $[1, maxPos]$，当且仅当已开的数量填满了这个区间，即 已开数量 == maxPos。若已开数量小于 maxPos，区间里必然有空洞，前缀就断了；已开数量不可能大于 maxPos，因为所有已开编号都 $\le maxPos$。

再把排列这条性质代进去：已开数量恒为 $i+1$。于是判定条件塌缩成一行 —— 第 $i$ 步前缀一致 $\iff$ maxPos == i + 1。

由此得到贯穿全程的不变量：扫描到下标 $i$ 时，maxPos = max(flips[0..i]) 表示已开编号的上界，i + 1 表示已开编号的个数；两者相等等价于 $[1, maxPos]$ 被恰好填满、无空洞。整个算法就是一边维护前缀最大值，一边把这个等式的成立次数累加起来。

解题步骤

初始化 maxPos = 0、answer = 0。maxPos 取 $0$ 是因为编号从 $1$ 起，$0$ 是「一个都没开」的合法下界，不会污染后续取最大值。

从左到右单次遍历 flips，因为题目问的是「每一步之后」的状态，天然要求按时间顺序推进，不能排序也不能跳步。

每步先更新 maxPos = max(maxPos, flips[i])，把当前打开的编号并入上界。必须先更新再判断：本步打开的灯泡是当前状态的一部分，先判断会漏掉它。

再检查 maxPos == i + 1，成立则 answer++。这里的 i + 1 直接充当「已开数量」，不需要另设计数器——排列的性质保证了它一定等于打开次数。

返回 answer。

以 flips = [3, 2, 4, 1, 5] 走一遍：

$i = 0$：flips[0] = 3，maxPos = 3，已开数量 $1$；$3 \ne 1$，已开集合是 ${3}$，$1$ 和 $2$ 是空洞，不计数。
$i = 1$：flips[1] = 2，maxPos 仍是 $3$，已开数量 $2$；$3 \ne 2$，集合 ${2,3}$ 缺 $1$，不计数。
$i = 2$：flips[2] = 4，maxPos = 4，已开数量 $3$；$4 \ne 3$，集合 ${2,3,4}$ 仍缺 $1$，不计数。
$i = 3$：flips[3] = 1，maxPos 仍是 $4$，已开数量 $4$；$4 = 4$ 成立，集合 ${1,2,3,4}$ 正是前缀，answer = 1。
$i = 4$：flips[4] = 5，maxPos = 5，已开数量 $5$；$5 = 5$ 成立，全开，answer = 2。

返回 $2$。注意第 $3$ 步这一刻，那个迟到的 $1$ 一口气把前面积压的三个空洞全部补齐，maxPos 却一步没动 —— 这正是「上界不变、数量追平」的典型时刻，也是这个判据比逐位扫描聪明的地方。

代码实现

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

        for (int i = 0; i < flips.length; i++) {
            // 先并入本步打开的编号，maxPos 始终是已开编号的上界。
            maxPos = Math.max(maxPos, flips[i]);
            // 已开数量恒为 i + 1，相等说明 [1, maxPos] 被填满、无空洞。
            if (maxPos == i + 1) {
                answer++;
            }
        }

        return answer;
    }
}

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

    for i, pos := range flips {
        // 先并入本步打开的编号，maxPos 始终是已开编号的上界。
        if pos > maxPos {
            maxPos = pos
        }
        // 已开数量恒为 i + 1，相等说明 [1, maxPos] 被填满、无空洞。
        if maxPos == i+1 {
            answer++
        }
    }

    return answer
}

复杂度分析

时间复杂度：$O(n)$。只做一趟遍历，循环体内是一次取最大值、一次相等比较和一次自增，全是常数操作，没有任何回头扫描。

空间复杂度：$O(1)$。只用了 maxPos 和 answer 两个整型变量，不需要布尔数组或哈希表来记录哪些灯被打开——排列性质已经把这份信息压缩进了下标 $i$。

关键点总结

把集合形态的判定（「是不是一个前缀」）转成两个标量的比较（「最大值 == 计数」），是这类题的核心动作；只要元素互不相同且全部 $\le$ 最大值，「填满」就等价于「数量 == 最大值」。

输入是排列这一条要主动用足：它同时给出了「无重复」和「第 $i$ 步已开 $i+1$ 个」两个免费结论，省掉了一个计数器和一个去重结构。

前缀最大值是一个可 $O(1)$ 增量维护的量，凡是判据只依赖前缀极值的题，都能把 $O(n^2)$ 的重复扫描压成一趟。

面试视角：面试官真正想听的是你如何证明「maxPos == i+1 等价于前缀一致」这两个方向——已开编号都 $\le maxPos$ 所以数量不会超，数量相等则区间无空洞。能把这层双向论证说清楚，比写出四行代码重要得多。

这个套路可以迁移到「最多能完成排序的块」一类问题：那里判据是前缀最大值等于下标，本质是同一个「前缀自洽」的观察。

易错点总结

先判断再更新 maxPos：flips = [1] 时，若在 maxPos 还是 $0$ 时就比较，$0 \ne 1$，返回 $0$，正确答案是 $1$。

用 i 而不是 i + 1 当已开数量：flips = [1, 2] 时会在 $i=0$ 判 $1 \ne 0$ 漏掉，在 $i=1$ 判 $2 \ne 1$ 又漏掉，返回 $0$，正确答案是 $2$。

误以为 flips[i] == i + 1 才算数：flips = [3, 2, 1] 时三步都不满足这个式子，返回 $0$；而实际第三步 $maxPos = 3 = i+1$ 是前缀一致的，答案应为 $1$。

额外开一个 count 变量却忘记自增：flips = [1, 2, 3] 时 count 恒为 $0$，maxPos 一路增大，永不相等，返回 $0$ 而非 $3$。

真的维护布尔数组并每步全扫：n = 10^5 且 flips = [1, 2, ..., n] 时是 $10^{10}$ 量级的比较，直接超时。

把编号当成下标直接访问数组：flips 的值域是 $[1, n]$，写 open[flips[i]] 而数组只开 n 长会在 flips[i] == n 时越界。

误判最后一步：忘记全开也算前缀一致而在循环里写 i < n - 1，flips = [1] 时循环不执行，返回 $0$。

对 flips 排序后再处理：排序后 flips 变成 $[1..n]$，任何输入都返回 $n$，flips = [3,2,4,1,5] 会错答成 $5$。

maxPos 初值设成 flips[0] 且循环从 $i=1$ 开始：漏掉第 $0$ 步的判定，flips = [1, 2] 只会返回 $1$。

相似题目

题目	难度	考察点
769. 最多能完成排序的块	中等	输入同为 $0..n-1$ 的排列，判据换成前缀最大值等于下标，切块而非计数
768. 最多能完成排序的块 II	困难	允许重复元素，排列性质失效，需改用前缀最大值与后缀最小值对比
763. 划分字母区间	中等	维护的是每个字符最后出现位置的最大值，边界处切分而非累加计数
55. 跳跃游戏	中等	同为维护前缀能达到的最远位置，但判据是可达性而非相等
128. 最长连续序列	中等	同样在找「连续无空洞」，但元素无序且需哈希集合从起点向后延伸
697. 数组的度	简单	一趟扫描同时维护首次出现位置与频次，靠三个映射而非单一极值
962. 最大宽度坡	中等	前缀最小值构成单调栈后倒序匹配，维护的极值用于配对而非自洽判定