题目描述
思路解析动画文字版
记牢一句:已点亮个数恒等于步数 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题