二进制字符串前缀一致的次数 图解题解
这道题到底在问什么
- 输入
- flips=[3,2,4,1,5]
- 输出
- 2
- 输入
- flips=[4,1,2,3]
- 输出
- 1
- 输入
- flips=[5,1,4,2,3]
- 输出
- 1
最优解：一步一步想明白
- 3记牢一句:已点亮个数恒等于步数 i,只要已点亮的最大编号 mx 也等于 i,就说明灯正好铺满 1 到 i 号,前缀一致计一次。
- 4上面这排是 8 盏灯,编号 1 到 8,现在全灭,二进制串是 00000000。翻灯脚本 flips = [2,1,4,3,5,7,6,8],意思是第 1 步点 2 号、第 2 步点 1 号,以此类推。开翻之前先说好盯两个数:已点亮个数(等于步数 i)和已点亮的最大编号 mx。
- 5第 1 步,按脚本把 2 号灯点亮(紫色这盏),它从灭变亮。场上现在亮了 1 盏,串是 01000000。亮着的灯里编号最大的是 2 号,所以 mx 更新成 2。
- 6拿最大编号 mx = 2 跟已点亮个数 1 比:mx 更大。这说明 2 号灯已经亮了,可前面 1 到 1 号里还有灭着的空位(标红那盏),串是 01000000,前缀没铺满。不是前缀一致,跳过,次数仍是 0。
- 7第 2 步,按脚本把 1 号灯点亮(紫色这盏),它从灭变亮。场上现在亮了 2 盏,串是 11000000。亮着的灯里编号最大的是 2 号,所以 mx 更新成 2。
- 8拿最大编号 mx = 2 跟已点亮个数 2 比:正好相等。相等就说明这 2 盏亮灯的编号恰好是 1 到 2,没有跳号,1 到 2 号铺成一整段、后面全灭。前缀一致,计一次,现在是第 1 次。
- 9看这一刻:1 到 2 号连成一整块亮着,串是 11000000,前面一长串 1、后面全是 0,干干净净的前缀。这正是题目要数的前缀一致时刻,把它记进答案,已经数到 1 次了。
- 10第 3 步,按脚本把 4 号灯点亮(紫色这盏),它从灭变亮。场上现在亮了 3 盏,串是 11010000。亮着的灯里编号最大的是 4 号,所以 mx 更新成 4。
- 11拿最大编号 mx = 4 跟已点亮个数 3 比:mx 更大。这说明 4 号灯已经亮了,可前面 1 到 3 号里还有灭着的空位(标红那盏),串是 11010000,前缀没铺满。不是前缀一致,跳过,次数仍是 1。
- 12第 4 步,按脚本把 3 号灯点亮(紫色这盏),它从灭变亮。场上现在亮了 4 盏,串是 11110000。亮着的灯里编号最大的是 4 号,所以 mx 更新成 4。
- 13拿最大编号 mx = 4 跟已点亮个数 4 比:正好相等。相等就说明这 4 盏亮灯的编号恰好是 1 到 4,没有跳号,1 到 4 号铺成一整段、后面全灭。前缀一致,计一次,现在是第 2 次。
- 14看这一刻:1 到 4 号连成一整块亮着,串是 11110000,前面一长串 1、后面全是 0,干干净净的前缀。这正是题目要数的前缀一致时刻,把它记进答案,已经数到 2 次了。
- 15第 5 步,按脚本把 5 号灯点亮(紫色这盏),它从灭变亮。场上现在亮了 5 盏,串是 11111000。亮着的灯里编号最大的是 5 号,所以 mx 更新成 5。
- 16拿最大编号 mx = 5 跟已点亮个数 5 比:正好相等。相等就说明这 5 盏亮灯的编号恰好是 1 到 5,没有跳号,1 到 5 号铺成一整段、后面全灭。前缀一致,计一次,现在是第 3 次。
- 17看这一刻:1 到 5 号连成一整块亮着,串是 11111000,前面一长串 1、后面全是 0,干干净净的前缀。这正是题目要数的前缀一致时刻,把它记进答案,已经数到 3 次了。
- 18第 6 步,按脚本把 7 号灯点亮(紫色这盏),它从灭变亮。场上现在亮了 6 盏,串是 11111010。亮着的灯里编号最大的是 7 号,所以 mx 更新成 7。
- 19拿最大编号 mx = 7 跟已点亮个数 6 比:mx 更大。这说明 7 号灯已经亮了,可前面 1 到 6 号里还有灭着的空位(标红那盏),串是 11111010,前缀没铺满。不是前缀一致,跳过,次数仍是 3。
- 20第 7 步,按脚本把 6 号灯点亮(紫色这盏),它从灭变亮。场上现在亮了 7 盏,串是 11111110。亮着的灯里编号最大的是 7 号,所以 mx 更新成 7。
- 21拿最大编号 mx = 7 跟已点亮个数 7 比:正好相等。相等就说明这 7 盏亮灯的编号恰好是 1 到 7,没有跳号,1 到 7 号铺成一整段、后面全灭。前缀一致,计一次,现在是第 4 次。
- 22看这一刻:1 到 7 号连成一整块亮着,串是 11111110,前面一长串 1、后面全是 0,干干净净的前缀。这正是题目要数的前缀一致时刻,把它记进答案,已经数到 4 次了。
- 23第 8 步,按脚本把 8 号灯点亮(紫色这盏),它从灭变亮。场上现在亮了 8 盏,串是 11111111。亮着的灯里编号最大的是 8 号,所以 mx 更新成 8。
- 24拿最大编号 mx = 8 跟已点亮个数 8 比:正好相等。相等就说明这 8 盏亮灯的编号恰好是 1 到 8,没有跳号,1 到 8 号铺成一整段、后面全灭。前缀一致,计一次,现在是第 5 次。
- 25看这一刻:1 到 8 号连成一整块亮着,串是 11111111,整排都是 1、已经没有后缀了,前缀铺满整排。这正是题目要数的前缀一致时刻,把它记进答案,已经数到 5 次了。
- 26八步全翻完,灯全亮,串是 11111111。回头看,前缀一致出现在第 2、4、5、7、8 步,正好是 mx 跟步数 i 相等的那几步,一共 5 次,跟开头说的答案对上了。全程没真去维护那串灯,只靠最大编号和步数两个数一路比下来。
⚠️ 容易写错的地方
✗ 错：真的拿一个数组维护那串灯,每步从头扫一遍看是否前缀一致
✓ 对：只维护已点亮的最大编号 mx,判 mx 是否等于步数 i
每步重扫整串是 O(n),总共 O(n²);利用「已点亮个数恒为 i」,只需一次 mx 与 i 的比较就判完,把每步压成常数
✗ 错：把判定写成 mx ≥ i 或 mx 大于 i 也算
✓ 对：必须是 mx 恰好等于 i 才前缀一致
mx 永远大于等于 i(i 个不同正整数,最大的至少是 i),只有取等才表示这 i 盏灯正好是 1 到 i、没有跳号;mx 比 i 大时前缀里一定还留着灭灯,不算
✗ 错：担心 flips 里有重复或 0,额外去算已点亮个数
✓ 对：题目保证 flips 是 1 到 n 的排列,第 i 步后必有 i 盏亮灯
正因是排列,前 i 步点的是 i 个互不相同的编号,已点亮个数就等于 i,可以直接用步数 i 代替,不必再开计数器数灯
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int numTimesAllBlue(vector<int>& flips) {
int ans = 0, mx = 0;
for (int i = 1; i <= flips.size(); ++i) {
mx = max(mx, flips[i - 1]);
ans += mx == i;
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int numTimesAllBlue(int[] flips) {
int ans = 0, mx = 0;
for (int i = 1; i <= flips.length; ++i) {
mx = Math.max(mx, flips[i - 1]);
if (mx == i) {
++ans;
}
}
return ans;
}
}复杂度
时间
O(n)
n 为 flips 长度。从头到尾扫一遍,每一步只做一次取最大、一次相等比较、可能一次自增,都是常数,整体就是一遍线性扫描
空间
O(1)
自始至终只用了最大编号 mx 与计数器 ans 两个整数,没有额外开数组或真去维护那串灯,峰值占用是常数,跟 n 多大无关
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 二进制字符串前缀一致的次数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么「已点亮个数」一定等于步数 i,可以省掉计数器?+
因为 flips 是 1 到 n 的排列,每一步点亮的都是一个之前没点过的新编号,而且都是从灭变亮、不会反复。所以走到第 i 步,场上恰好积累了 i 盏不同编号的亮灯,个数就是 i,直接拿步数 i 当亮灯个数用,不必再开一个变量去数。
为什么最大编号 mx 永远不小于 i,只能等于或大于?+
前 i 步点亮了 i 个互不相同的正整数编号。i 个不同的正整数,最大的那个至少是 i,因为最省的情形就是 1 到 i,这时最大正好是 i;只要有任何一个编号跳到 i 以上,最大就更大。所以 mx 总是大于等于 i。取等当且仅当这 i 个编号正好是 1 到 i,没有跳号,此刻 1 到 i 全亮、其余全灭,正是前缀一致。
复杂度和会不会溢出?+
一遍扫描,时间 O(n);只用最大编号 mx、计数器 ans、循环变量 i 几个整数,空间 O(1)。题目里 n 最多 5 万、编号最多 5 万,这些值远在 32 位 int 的二十一亿上限之内,用 int 完全安全。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 二进制字符串前缀一致的次数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。