表现良好的最长时间段 图解题解
这道题到底在问什么
- 输入
- hours = [9,9,6]
- 输出
- 3（两个劳累日 > 一个非劳累日）
最优解：一步一步想明白
- 3两套判定：score>0 时整段 [0..i] 合格；score≤0 时去哈希表查 first[score−1] 配出区间。哈希表只记每个前缀和最早的下标。下面逐天演示。
- 4开始前：前缀和 score = 0，答案 best = 0，哈希表 first 还是空的。指针 i 从下标 0 出发。
- 5指针 i 走到下标 0：工作 6 小时 ≤ 8 → 非劳累日，记 −1。
- 6score = -1 ≤ 0，去查更早出现过 -2 的位置，但表里还没有，所以这一步没找到合格区间，best 仍是 0。
- 7前缀和 -1 还是第一次见，把它的最早下标 0 记进哈希表（只记最早一次，区间才最长）。
- 8指针 i 走到下标 1：工作 6 小时 ≤ 8 → 非劳累日，记 −1。
- 9score = -2 ≤ 0，去查更早出现过 -3 的位置，但表里还没有，所以这一步没找到合格区间，best 仍是 0。
- 10前缀和 -2 还是第一次见，把它的最早下标 1 记进哈希表（只记最早一次，区间才最长）。
- 11指针 i 走到下标 2：工作 6 小时 ≤ 8 → 非劳累日，记 −1。
- 12score = -3 ≤ 0，去查更早出现过 -4 的位置，但表里还没有，所以这一步没找到合格区间，best 仍是 0。
- 13前缀和 -3 还是第一次见，把它的最早下标 2 记进哈希表（只记最早一次，区间才最长）。
- 14指针 i 走到下标 3：工作 9 小时 > 8 → 劳累日，记 +1。
- 15score = -2 ≤ 0，去查更早出现过 -3 的位置：first[-3] = 2。那么从下标 3 到 3 这段分数正好 > 0，长度 1。best 刷新为 1。
- 16前缀和 -2 之前已经出现过，哈希表里保留它最早的下标 1，不覆盖——这样配出的区间才最长。
- 17指针 i 走到下标 4：工作 9 小时 > 8 → 劳累日，记 +1。
- 18score = -1 ≤ 0，去查更早出现过 -2 的位置：first[-2] = 1。那么从下标 2 到 4 这段分数正好 > 0，长度 3。best 刷新为 3。
- 19前缀和 -1 之前已经出现过，哈希表里保留它最早的下标 0，不覆盖——这样配出的区间才最长。
- 20指针 i 走到下标 5：工作 9 小时 > 8 → 劳累日，记 +1。
- 21score = 0 ≤ 0，去查更早出现过 -1 的位置：first[-1] = 0。那么从下标 1 到 5 这段分数正好 > 0，长度 5。best 刷新为 5。
- 22前缀和 0 还是第一次见，把它的最早下标 5 记进哈希表（只记最早一次，区间才最长）。
- 23指针 i 走到下标 6：工作 6 小时 ≤ 8 → 非劳累日，记 −1。
- 24score = -1 ≤ 0，去查更早出现过 -2 的位置：first[-2] = 1。那么从下标 2 到 6 这段分数正好 > 0，长度 5。没超过现有 best=5。
- 25前缀和 -1 之前已经出现过，哈希表里保留它最早的下标 0，不覆盖——这样配出的区间才最长。
- 26指针 i 走到下标 7：工作 6 小时 ≤ 8 → 非劳累日，记 −1。
- 27score = -2 ≤ 0，去查更早出现过 -3 的位置：first[-3] = 2。那么从下标 3 到 7 这段分数正好 > 0，长度 5。没超过现有 best=5。
- 28前缀和 -2 之前已经出现过，哈希表里保留它最早的下标 1，不覆盖——这样配出的区间才最长。
- 29指针 i 走到下标 8：工作 6 小时 ≤ 8 → 非劳累日，记 −1。
- 30score = -3 ≤ 0，去查更早出现过 -4 的位置，但表里还没有，所以这一步没找到合格区间，best 仍是 5。
- 31前缀和 -3 之前已经出现过，哈希表里保留它最早的下标 2，不覆盖——这样配出的区间才最长。
- 32扫描结束。整趟里最长的「累 > 不累」区间是高亮的下标 1 到 5（共 5 天），best=5 就是答案。
⚠️ 容易写错的地方
✗ 错：哈希表里覆盖同一个 score 的下标
✓ 对：只记每个 score 第一次出现的下标
要让区间 (j, i] 最长，j 必须尽量靠左，所以保留最早那次，绝不覆盖
✗ 错：score>0 时还去查哈希表
✓ 对：score>0 直接用 i+1，整段都合格
从开头到 i 的总分已 >0，整段就是合格区间，比任何子区间都长
✗ 错：查的是 first[score] 而不是 first[score−1]
✓ 对：score≤0 时查 first[score−1]
要让 (j, i] 这段和 >0，需要 score(i) − score(j) ≥ 1，即 score(j) = score−1
完整代码（Python / C++ / Java）
Python
def longestWPI(hours):
score = best = 0
first = {} # 前缀和 -> 最早下标
for i, h in enumerate(hours):
score += 1 if h > 8 else -1
if score > 0: # 整段 [0..i] 合格
best = i + 1
elif score - 1 in first: # 区间 (j..i] 合格
best = max(best, i - first[score - 1])
if score not in first: # 只记最早一次
first[score] = i
return bestC++
int longestWPI(vector<int>& hours){
int score = 0, best = 0;
unordered_map<int,int> first;
for (int i = 0; i < hours.size(); i++) {
score += hours[i] > 8 ? 1 : -1;
if (score > 0) best = i + 1;
else if (first.count(score - 1))
best = max(best, i - first[score - 1]);
if (!first.count(score)) first[score] = i;
}
return best;
}Java
public int longestWPI(int[] hours) {
int score = 0, best = 0;
Map<Integer,Integer> first = new HashMap<>();
for (int i = 0; i < hours.length; i++) {
score += hours[i] > 8 ? 1 : -1;
if (score > 0) best = i + 1;
else if (first.containsKey(score - 1))
best = Math.max(best, i - first.get(score - 1));
first.putIfAbsent(score, i);
}
return best;
}复杂度
时间
O(n)
指针 i 把数组扫一遍，每步哈希查/存都是 O(1)
空间
O(n)
哈希表 first 最多存 n 个不同的前缀和
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 表现良好的最长时间段 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么把 >8 小时记 +1、否则记 −1 就能解？+
「劳累日数量 > 非劳累日数量」等价于「这段里 +1 的个数 > −1 的个数」，也就是这段的和 > 0。于是问题变成「找和 > 0 的最长连续子段」，用前缀和处理。
哈希表为什么只存每个前缀和第一次出现的下标？+
因为我们要的是最长区间。固定右端 i，左端 j 越靠左区间越长。同一个前缀和值，最早那次下标最小，所以只保留第一次、不覆盖。
score > 0 和 score ≤ 0 两个分支能合并吗？+
可以但不划算。score>0 时整段 [0..i] 合格、长度 i+1，是直接最优，不必查表；只有 score≤0 才需要靠 first[score−1] 去配一个更短的合格区间。分开写更清晰也更快。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 表现良好的最长时间段 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。