题目描述
思路解析动画文字版
记牢这一句:分界线右移一格,吃进一个 0 就加 1 分,吃进一个 1 就扣 1 分。下面从下标 0 开始,分界线一步步往右走。
先看整条数组 · 明确挪一格的加减规则：先把整条数组看清楚。这里面有 3 个 1、5 个 0。全绿表示此刻它们都还在右段。核心规则只有一句:分界线每往右挪一格,吃进的那个元素若是 0,左段多一个 0,分数加 1;若是 1,右段少一个 1,分数减 1。把这条记牢,后面每一帧都在套它。
分界线放在下标 0 · 左段为空,右段吃下全部：分界线先摆在最左边下标 0 这里,左段是空的,一个 0 都没有,l0 = 0;右段吃下了全部元素,里头 1 有 3 个,r1 = 3。这一切点的分数就是 0 加 3,等于 3。
设下标 0 为初始擂主 · mx = 3,答案 = [0]：既然下标 0 是我们算出的第一个分数,就先把它当擂主:历史最高 mx 记成 3,答案下标 ans 记成 [0]。接下来分界线一格一格往右挪,谁的分数超过擂主就换人,谁跟擂主打平就一起收进答案。
分界线挪到下标 1 · 吃进 nums[0] = 0：分界线往右挪一格到下标 1,紫色这个 nums[0] 从右段交到左段。它是 0,是个 0,左段会多出一个 0,分数要往上加 1。先看清它是谁,下一帧结算新分数。
结算下标 1 · 分数 t = 4 · 刷新最高 mx = 4：吃进的是 0,左段 0 个数 l0 变成 1,分数升到 4。这比之前的最高分还高,换擂主,最高 mx 更新成 4,答案只留下标 1。
分界线挪到下标 2 · 吃进 nums[1] = 0：分界线往右挪一格到下标 2,紫色这个 nums[1] 从右段交到左段。它是 0,是个 0,左段会多出一个 0,分数要往上加 1。先看清它是谁,下一帧结算新分数。
结算下标 2 · 分数 t = 5 · 刷新最高 mx = 5：吃进的是 0,左段 0 个数 l0 变成 2,分数升到 5。这比之前的最高分还高,换擂主,最高 mx 更新成 5,答案只留下标 2。
分界线挪到下标 3 · 吃进 nums[2] = 1：分界线往右挪一格到下标 3,紫色这个 nums[2] 从右段交到左段。它是 1,是个 1,右段会少掉一个 1,分数要往下扣 1。先看清它是谁,下一帧结算新分数。
结算下标 3 · 分数 t = 4 · 低于最高 5,跳过：吃进的是 1,右段 1 个数 r1 变成 2,分数降到 4。这没超过当前最高分 5,擂主不换,答案也不动。
分界线挪到下标 4 · 吃进 nums[3] = 0：分界线往右挪一格到下标 4,紫色这个 nums[3] 从右段交到左段。它是 0,是个 0,左段会多出一个 0,分数要往上加 1。先看清它是谁,下一帧结算新分数。
结算下标 4 · 分数 t = 5 · 与最高 5 打平,收入答案：吃进的是 0,左段 0 个数 l0 变成 3,分数升到 5。这跟当前最高分 5 正好打平,不能丢,把下标 4 也追加进答案,现在答案是 [2,4]。
分界线挪到下标 5 · 吃进 nums[4] = 1：分界线往右挪一格到下标 5,紫色这个 nums[4] 从右段交到左段。它是 1,是个 1,右段会少掉一个 1,分数要往下扣 1。先看清它是谁,下一帧结算新分数。
结算下标 5 · 分数 t = 4 · 低于最高 5,跳过：吃进的是 1,右段 1 个数 r1 变成 1,分数降到 4。这没超过当前最高分 5,擂主不换,答案也不动。
分界线挪到下标 6 · 吃进 nums[5] = 1：分界线往右挪一格到下标 6,紫色这个 nums[5] 从右段交到左段。它是 1,是个 1,右段会少掉一个 1,分数要往下扣 1。先看清它是谁,下一帧结算新分数。
结算下标 6 · 分数 t = 3 · 低于最高 5,跳过：吃进的是 1,右段 1 个数 r1 变成 0,分数降到 3。这没超过当前最高分 5,擂主不换,答案也不动。
分界线挪到下标 7 · 吃进 nums[6] = 0：分界线往右挪一格到下标 7,紫色这个 nums[6] 从右段交到左段。它是 0,是个 0,左段会多出一个 0,分数要往上加 1。先看清它是谁,下一帧结算新分数。
结算下标 7 · 分数 t = 4 · 低于最高 5,跳过：吃进的是 0,左段 0 个数 l0 变成 4,分数升到 4。这没超过当前最高分 5,擂主不换,答案也不动。
分界线挪到下标 8 · 吃进 nums[7] = 0：分界线往右挪一格到下标 8,紫色这个 nums[7] 从右段交到左段。它是 0,是个 0,左段会多出一个 0,分数要往上加 1。先看清它是谁,下一帧结算新分数。
结算下标 8 · 分数 t = 5 · 与最高 5 打平,收入答案：吃进的是 0,左段 0 个数 l0 变成 5,分数升到 5。这跟当前最高分 5 正好打平,不能丢,把下标 8 也追加进答案,现在答案是 [2,4,8]。
扫描完成 · 最高分 5,取得最高分的下标是 2、4、8：分界线走到了最右端,全部 9 个切点都算过了。这组数据的得分一路是 3、4、5、4、5、4、3、4、5,峰值是 5,在下标 2、4、8 这几处并列拿到。它们就是答案。判定始终只看一条:每个切点的分数,等于左段 0 的个数加右段 1 的个数。
边界想清:全 0 时切最右、全 1 时切最左、单个 0 时切到它右边把它收进左段。
面试重点:分界线右移做增量计数、O(n) 完成、平局要收集全部下标。
参考代码
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 maxScoreIndices(self, nums: List[int]) -> List[int]: l0, r1 = 0, sum(nums) mx = r1 ans = [0] for i, x in enumerate(nums, 1): l0 += x ^ 1 r1 -= x t = l0 + r1 if mx == t: ans.append(i) elif mx < t: mx = t ans = [i] return ans复杂度
- 时间：O(n)，先求一次数组和是 O(n),再从左到右扫一遍 n 个切点,每个切点只做常数次加减和比较,合起来还是线性
- 空间：O(1)，按峰值算。除去要返回的答案列表,只用了 l0、r1、mx、t 这几个整数变量,不随 n 增长;答案列表是必须的输出,不计入额外空间
易错点
面试追问把动画讲成自己的话
追问这题的核心思路是什么?
追问为什么不能每个切点都重新数一遍?
追问出现多个最高分下标时怎么处理?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
制造字母异位词的最小步骤数 II
LeetCode 2186 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题