题目描述
思路解析
一句话答案：LeetCode 1375 二进制字符串前缀一致的次数用一次遍历：flips 是排列，第 i 步后必有 i 盏亮灯，只要已亮最大编号 mx 也等于 i，就说明 1 到 i 恰好铺满、计一次。时间 O(n)、空间 O(1)。
n 盏灯按脚本一步步点亮，这道题在数哪些时刻
给一排 n 盏灯，编号 1 到 n，初始全灭。flips 是翻灯脚本，第 i 步点亮 flips[i] 号灯。每翻一步看一眼：亮灯是不是正好铺满 1 到 i 号、其余全灭；是就算一次「前缀一致」，题目数出这样的时刻共几次，题面 flips=[3,2,4,1,5] 答案是 2。记牢一个前提：flips 是 1 到 n 的排列，第 i 步后场上恰好亮 i 盏灯。
每步都把整串灯从头核对一遍，会慢在哪里
一个直白做法是真开长度 n 的数组模拟那排灯，每翻亮一盏就从头扫一遍看前缀是否铺满 1 到 i 号。可每步扫描都走 O(n)，n 步累计 O(n²)；flips 长到 5 万时，两万五千步各扫五万格，重复得太厉害。慢在每步都从头核对，把上一步已确认的前缀又白数一遍。
已亮个数恒等于步数，前缀铺没铺满只看一个数
抓住排列这个前提，能把整串扫描省掉。前 i 步点亮的是 i 个互不相同的编号（不重复、也没有 0），每盏只从灭变亮、不反复，所以第 i 步时亮灯个数恒等于 i。个数既已钉死是 i，判前缀有没有铺满 1 到 i 就只剩一件事：这 i 个编号是不是正好占着 1 到 i、中间没跳号。
而有没有跳号，只看已亮灯的最大编号 mx 就够。i 个不同正整数里最大的至少是 i——最省的排法是 1 到 i，此时正好等于 i；只要有编号跳到 i 以上就更大，所以 mx 恒 ≥ i。取等 mx == i，当且仅当这 i 个编号正好铺满 1 到 i；一旦 mx ＞ i，前 i 号里必还留着空位。所以每步把当前编号并进 mx、再看是否等于步数 i，判定就压成常数。
边走边更新最大编号，撞上相等就记一笔
只养两个整数：mx 记已亮灯的最大编号，ans 记前缀一致次数，都从 0 起。每步做三件事：读到点亮的编号 x，先 mx = max(mx, x)；再拿 mx 跟步数 i 比，相等就 ans 加一，不等跳过；进下一步。全程不碰那排灯，一遍扫到底返回 ans。
顺着题面 [3,2,4,1,5]，逐步对齐 mx 和步数
起手 mx=0、ans=0。第 1 步点 3 号，mx=max(0,3)=3 ＞ 步数 1，前缀还空，跳过。第 2 步点 2 号，mx=max(3,2)=3 ＞ 2，仍空，跳过。第 3 步点 4 号，mx=max(3,4)=4 ＞ 3，跳过。第 4 步点 1 号，mx=max(4,1)=4 与步数 4 相等，1 到 4 号铺满，ans 变 1。第 5 步点 5 号，mx=max(4,5)=5 与步数 5 相等，1 到 5 号铺满，ans 变 2。返回 2。
判定放宽成 mx ≥ i，就会把没铺满的时刻也算进去
一遍扫描、每步一次取最大加一次比较，时间 O(n)；全程只有 mx 和 ans 两个整数，没真开那排灯，空间 O(1)。两处容易写歪。一是把判定放宽成 mx ≥ i 或 mx ＞ i：因为 mx 恒 ≥ i，几乎每步都误判成前缀一致，必须卡死恰好等于 i。二是不放心排列前提，另开计数器数亮灯个数：题目已保证 flips 是排列，第 i 步后必有 i 盏亮灯，拿步数 i 当亮灯数即可，多养一个变量反而添乱。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢一句:已点亮个数恒等于步数 i,只要已点亮的最大编号 mx 也等于 i,就说明灯正好铺满 1 到 i 号,前缀一致计一次。
总览 · 八盏灯全灭,翻灯脚本 flips = [2,1,4,3,5,7,6,8]：上面这排是 8 盏灯,编号 1 到 8,现在全灭,二进制串是 00000000。翻灯脚本 flips = [2,1,4,3,5,7,6,8],意思是第 1 步点 2 号、第 2 步点 1 号,以此类推。开翻之前先说好盯两个数:已点亮个数(等于步数 i)和已点亮的最大编号 mx。
翻灯 · 第 1 步点亮 2 号：第 1 步,按脚本把 2 号灯点亮(紫色这盏),它从灭变亮。场上现在亮了 1 盏,串是 01000000。亮着的灯里编号最大的是 2 号,所以 mx 更新成 2。
判定 · mx = 2 大于步数 1：拿最大编号 mx = 2 跟已点亮个数 1 比:mx 更大。这说明 2 号灯已经亮了,可前面 1 到 1 号里还有灭着的空位(标红那盏),串是 01000000,前缀没铺满。不是前缀一致,跳过,次数仍是 0。
翻灯 · 第 2 步点亮 1 号：第 2 步,按脚本把 1 号灯点亮(紫色这盏),它从灭变亮。场上现在亮了 2 盏,串是 11000000。亮着的灯里编号最大的是 2 号,所以 mx 更新成 2。
判定 · mx = 2 与步数 2 相等：拿最大编号 mx = 2 跟已点亮个数 2 比:正好相等。相等就说明这 2 盏亮灯的编号恰好是 1 到 2,没有跳号,1 到 2 号铺成一整段、后面全灭。前缀一致,计一次,现在是第 1 次。
前缀一致时刻 · 1 到 2 号连成一片：看这一刻:1 到 2 号连成一整块亮着,串是 11000000,前面一长串 1、后面全是 0,干干净净的前缀。这正是题目要数的前缀一致时刻,把它记进答案,已经数到 1 次了。
翻灯 · 第 3 步点亮 4 号：第 3 步,按脚本把 4 号灯点亮(紫色这盏),它从灭变亮。场上现在亮了 3 盏,串是 11010000。亮着的灯里编号最大的是 4 号,所以 mx 更新成 4。
判定 · mx = 4 大于步数 3：拿最大编号 mx = 4 跟已点亮个数 3 比:mx 更大。这说明 4 号灯已经亮了,可前面 1 到 3 号里还有灭着的空位(标红那盏),串是 11010000,前缀没铺满。不是前缀一致,跳过,次数仍是 1。
翻灯 · 第 4 步点亮 3 号：第 4 步,按脚本把 3 号灯点亮(紫色这盏),它从灭变亮。场上现在亮了 4 盏,串是 11110000。亮着的灯里编号最大的是 4 号,所以 mx 更新成 4。
判定 · mx = 4 与步数 4 相等：拿最大编号 mx = 4 跟已点亮个数 4 比:正好相等。相等就说明这 4 盏亮灯的编号恰好是 1 到 4,没有跳号,1 到 4 号铺成一整段、后面全灭。前缀一致,计一次,现在是第 2 次。
前缀一致时刻 · 1 到 4 号连成一片：看这一刻:1 到 4 号连成一整块亮着,串是 11110000,前面一长串 1、后面全是 0,干干净净的前缀。这正是题目要数的前缀一致时刻,把它记进答案,已经数到 2 次了。
翻灯 · 第 5 步点亮 5 号：第 5 步,按脚本把 5 号灯点亮(紫色这盏),它从灭变亮。场上现在亮了 5 盏,串是 11111000。亮着的灯里编号最大的是 5 号,所以 mx 更新成 5。
判定 · mx = 5 与步数 5 相等：拿最大编号 mx = 5 跟已点亮个数 5 比:正好相等。相等就说明这 5 盏亮灯的编号恰好是 1 到 5,没有跳号,1 到 5 号铺成一整段、后面全灭。前缀一致,计一次,现在是第 3 次。
前缀一致时刻 · 1 到 5 号连成一片：看这一刻:1 到 5 号连成一整块亮着,串是 11111000,前面一长串 1、后面全是 0,干干净净的前缀。这正是题目要数的前缀一致时刻,把它记进答案,已经数到 3 次了。
翻灯 · 第 6 步点亮 7 号：第 6 步,按脚本把 7 号灯点亮(紫色这盏),它从灭变亮。场上现在亮了 6 盏,串是 11111010。亮着的灯里编号最大的是 7 号,所以 mx 更新成 7。
判定 · mx = 7 大于步数 6：拿最大编号 mx = 7 跟已点亮个数 6 比:mx 更大。这说明 7 号灯已经亮了,可前面 1 到 6 号里还有灭着的空位(标红那盏),串是 11111010,前缀没铺满。不是前缀一致,跳过,次数仍是 3。
翻灯 · 第 7 步点亮 6 号：第 7 步,按脚本把 6 号灯点亮(紫色这盏),它从灭变亮。场上现在亮了 7 盏,串是 11111110。亮着的灯里编号最大的是 7 号,所以 mx 更新成 7。
判定 · mx = 7 与步数 7 相等：拿最大编号 mx = 7 跟已点亮个数 7 比:正好相等。相等就说明这 7 盏亮灯的编号恰好是 1 到 7,没有跳号,1 到 7 号铺成一整段、后面全灭。前缀一致,计一次,现在是第 4 次。
前缀一致时刻 · 1 到 7 号连成一片：看这一刻:1 到 7 号连成一整块亮着,串是 11111110,前面一长串 1、后面全是 0,干干净净的前缀。这正是题目要数的前缀一致时刻,把它记进答案,已经数到 4 次了。
翻灯 · 第 8 步点亮 8 号：第 8 步,按脚本把 8 号灯点亮(紫色这盏),它从灭变亮。场上现在亮了 8 盏,串是 11111111。亮着的灯里编号最大的是 8 号,所以 mx 更新成 8。
判定 · mx = 8 与步数 8 相等：拿最大编号 mx = 8 跟已点亮个数 8 比:正好相等。相等就说明这 8 盏亮灯的编号恰好是 1 到 8,没有跳号,1 到 8 号铺成一整段、后面全灭。前缀一致,计一次,现在是第 5 次。
前缀一致时刻 · 1 到 8 号连成一片：看这一刻:1 到 8 号连成一整块亮着,串是 11111111,整排都是 1、已经没有后缀了,前缀铺满整排。这正是题目要数的前缀一致时刻,把它记进答案,已经数到 5 次了。
完成 · 答案 5 次：八步全翻完,灯全亮,串是 11111111。回头看,前缀一致出现在第 2、4、5、7、8 步,正好是 mx 跟步数 i 相等的那几步,一共 5 次,跟开头说的答案对上了。全程没真去维护那串灯,只靠最大编号和步数两个数一路比下来。
边界:顺序排列每步都对;大编号先亮会把前缀一致拖到最后;最后铺满那一步至少能成一次。
面试重点:排列让已点亮个数恒为 i、mx 永远大于等于 i 取等即铺满、整体 O(n) 时间 O(1) 空间不溢出。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def numTimesAllBlue(self, flips: List[int]) -> int: ans = mx = 0 for i, x in enumerate(flips, 1): mx = max(mx, x) ans += mx == i return ans复杂度
- 时间：O(n)，n 为 flips 长度。从头到尾扫一遍,每一步只做一次取最大、一次相等比较、可能一次自增,都是常数,整体就是一遍线性扫描
- 空间：O(1)，自始至终只用了最大编号 mx 与计数器 ans 两个整数,没有额外开数组或真去维护那串灯,峰值占用是常数,跟 n 多大无关
易错点
面试追问把动画讲成自己的话
追问为什么「已点亮个数」一定等于步数 i,可以省掉计数器?
追问为什么最大编号 mx 永远不小于 i,只能等于或大于?
追问复杂度和会不会溢出?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
找出第 N 个二进制字符串中的第 K 位
LeetCode 1545 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题