分组得分最高的所有下标 图解题解
这道题到底在问什么
- 输入
- nums=[0,0,1,0]
- 输出
- [2,4] (下标 2 和 4 都能拿到最高分 3)
- 输入
- nums=[1,1]
- 输出
- [0] (整段都归右侧,拿到 2 个 1,得分 2 最高)
最优解：一步一步想明白
- 3记牢这一句:分界线右移一格,吃进一个 0 就加 1 分,吃进一个 1 就扣 1 分。下面从下标 0 开始,分界线一步步往右走。
- 4先把整条数组看清楚。这里面有 3 个 1、5 个 0。全绿表示此刻它们都还在右段。核心规则只有一句:分界线每往右挪一格,吃进的那个元素若是 0,左段多一个 0,分数加 1;若是 1,右段少一个 1,分数减 1。把这条记牢,后面每一帧都在套它。
- 5分界线先摆在最左边下标 0 这里,左段是空的,一个 0 都没有,l0 = 0;右段吃下了全部元素,里头 1 有 3 个,r1 = 3。这一切点的分数就是 0 加 3,等于 3。
- 6既然下标 0 是我们算出的第一个分数,就先把它当擂主:历史最高 mx 记成 3,答案下标 ans 记成 [0]。接下来分界线一格一格往右挪,谁的分数超过擂主就换人,谁跟擂主打平就一起收进答案。
- 7分界线往右挪一格到下标 1,紫色这个 nums[0] 从右段交到左段。它是 0,是个 0,左段会多出一个 0,分数要往上加 1。先看清它是谁,下一帧结算新分数。
- 8吃进的是 0,左段 0 个数 l0 变成 1,分数升到 4。这比之前的最高分还高,换擂主,最高 mx 更新成 4,答案只留下标 1。
- 9分界线往右挪一格到下标 2,紫色这个 nums[1] 从右段交到左段。它是 0,是个 0,左段会多出一个 0,分数要往上加 1。先看清它是谁,下一帧结算新分数。
- 10吃进的是 0,左段 0 个数 l0 变成 2,分数升到 5。这比之前的最高分还高,换擂主,最高 mx 更新成 5,答案只留下标 2。
- 11分界线往右挪一格到下标 3,紫色这个 nums[2] 从右段交到左段。它是 1,是个 1,右段会少掉一个 1,分数要往下扣 1。先看清它是谁,下一帧结算新分数。
- 12吃进的是 1,右段 1 个数 r1 变成 2,分数降到 4。这没超过当前最高分 5,擂主不换,答案也不动。
- 13分界线往右挪一格到下标 4,紫色这个 nums[3] 从右段交到左段。它是 0,是个 0,左段会多出一个 0,分数要往上加 1。先看清它是谁,下一帧结算新分数。
- 14吃进的是 0,左段 0 个数 l0 变成 3,分数升到 5。这跟当前最高分 5 正好打平,不能丢,把下标 4 也追加进答案,现在答案是 [2,4]。
- 15分界线往右挪一格到下标 5,紫色这个 nums[4] 从右段交到左段。它是 1,是个 1,右段会少掉一个 1,分数要往下扣 1。先看清它是谁,下一帧结算新分数。
- 16吃进的是 1,右段 1 个数 r1 变成 1,分数降到 4。这没超过当前最高分 5,擂主不换,答案也不动。
- 17分界线往右挪一格到下标 6,紫色这个 nums[5] 从右段交到左段。它是 1,是个 1,右段会少掉一个 1,分数要往下扣 1。先看清它是谁,下一帧结算新分数。
- 18吃进的是 1,右段 1 个数 r1 变成 0,分数降到 3。这没超过当前最高分 5,擂主不换,答案也不动。
- 19分界线往右挪一格到下标 7,紫色这个 nums[6] 从右段交到左段。它是 0,是个 0,左段会多出一个 0,分数要往上加 1。先看清它是谁,下一帧结算新分数。
- 20吃进的是 0,左段 0 个数 l0 变成 4,分数升到 4。这没超过当前最高分 5,擂主不换,答案也不动。
- 21分界线往右挪一格到下标 8,紫色这个 nums[7] 从右段交到左段。它是 0,是个 0,左段会多出一个 0,分数要往上加 1。先看清它是谁,下一帧结算新分数。
- 22吃进的是 0,左段 0 个数 l0 变成 5,分数升到 5。这跟当前最高分 5 正好打平,不能丢,把下标 8 也追加进答案,现在答案是 [2,4,8]。
- 23分界线走到了最右端,全部 9 个切点都算过了。这组数据的得分一路是 3、4、5、4、5、4、3、4、5,峰值是 5,在下标 2、4、8 这几处并列拿到。它们就是答案。判定始终只看一条:每个切点的分数,等于左段 0 的个数加右段 1 的个数。
⚠️ 容易写错的地方
✗ 错：每个切点都重新去数一遍左段 0 和右段 1
✓ 对：维护 l0、r1,每步只做一次加减
重新数是每点 O(n)、总共 O(n²),会超时;分界线右移只改一个元素,增量更新才是 O(n)
✗ 错：忘了切点有 n+1 个,漏掉左段空或右段空
✓ 对：i 从 0 枚举到 n,两端都要算
i=0 是左段为空、i=n 是右段为空,最高分常常正好落在这两个极端,漏了就错
✗ 错：只返回第一个达到最高分的下标
✓ 对：打平时也要把下标收进答案
题目要的是全部最高分下标,平局要一起收集,不能只留一个
✗ 错：把得分算成左段 1 的个数或右段 0 的个数
✓ 对：左段数 0、右段数 1
方向记反会整个算错;记牢左段看 0、右段看 1
完整代码（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 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 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:
vector<int> maxScoreIndices(vector<int>& nums) {
int l0 = 0, r1 = accumulate(nums.begin(), nums.end(), 0);
int mx = r1;
vector<int> ans = {0};
for (int i = 1; i <= nums.size(); ++i) {
int x = nums[i - 1];
l0 += x ^ 1;
r1 -= x;
int t = l0 + r1;
if (mx == t) {
ans.push_back(i);
} else if (mx < t) {
mx = t;
ans = {i};
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public List<Integer> maxScoreIndices(int[] nums) {
int l0 = 0, r1 = Arrays.stream(nums).sum();
int mx = r1;
List<Integer> ans = new ArrayList<>();
ans.add(0);
for (int i = 1; i <= nums.length; ++i) {
int x = nums[i - 1];
l0 += x ^ 1;
r1 -= x;
int t = l0 + r1;
if (mx == t) {
ans.add(i);
} else if (mx < t) {
mx = t;
ans.clear();
ans.add(i);
}
}
return ans;
}
}复杂度
时间
O(n)
先求一次数组和是 O(n),再从左到右扫一遍 n 个切点,每个切点只做常数次加减和比较,合起来还是线性
空间
O(1)
按峰值算。除去要返回的答案列表,只用了 l0、r1、mx、t 这几个整数变量,不随 n 增长;答案列表是必须的输出,不计入额外空间
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 分组得分最高的所有下标 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题的核心思路是什么?+
把分界线从左往右扫,得分等于左段 0 的个数加右段 1 的个数。分界线每挪一格就把一个元素从右段交给左段:吃进 0 分数加 1、吃进 1 分数减 1。维护 l0 和 r1 两个计数,每步 O(1) 更新分数,一路记录最高分和取得最高分的所有下标。
为什么不能每个切点都重新数一遍?+
每个切点重新数是 O(n),n+1 个切点合起来 O(n²),数据一大就超时。分界线右移只影响被吃进的那一个元素,用增量更新把每步压到 O(1),整体才是 O(n)。这就是前缀计数的价值。
出现多个最高分下标时怎么处理?+
维护最高分 mx 和答案列表 ans。新分数比 mx 大就更新 mx 并把 ans 重置成只含当前下标;新分数和 mx 打平就把当前下标追加进 ans;比 mx 小就跳过。这样扫完一遍,ans 里就是全部并列最高的下标。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 分组得分最高的所有下标 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。