LeetCode 1124. 表现良好的最长时间段
题目描述
题意分析
一天工作时长严格大于八小时才算劳累，目标区间内劳累天数必须严格多于不劳累天数。将两类天数分别记为
+1、-1，区间和就等于两种天数之差，问题转为求和严格为正的最长连续区间。用前缀和表示区间和：若当前前缀分数为
score，某个更早前缀的分数为p，两者之间的区间合法当且仅当p < score。为了让区间最长，应找尽可能早的这样一个前缀。
解法：前缀和 + 最早位置
核心思路
[!blue]
score记录下标0到当前idx的前缀分数，first[p]保存分数p第一次出现时的结束下标，answer保存目前的最大长度。若first[p] = left，对应区间从left+1开始，到idx结束，长度为idx-left。当
score > 0时，从下标零开始的整个前缀已经合法，长度idx+1是以当前下标结尾能取得的最大长度，也比先前所有候选都长，所以直接更新answer。当
score <= 0时，只需查询first[score-1]。前缀分数从零出发，每一步只能增加或减少一；要到达任何小于score-1的分数，必定先经过score-1。因此它的最早出现位置，不会晚于其他所有小于score的候选前缀，而与当前分数相减恰好为一，确实构成合法区间。若它尚未出现，更低分数也不可能已经出现。每轮判断后，只在当前分数尚未记录时保存下标。对于同一个前缀分数，越早的位置给后续右端留下的区间越长，后来的位置没有替换价值。初始空前缀的分数为零、下标为负一；能用它的情况已由
score > 0单独处理，因此代码不需要预先把它加入映射。
解题步骤
- 逐天累加分数。
- 正分直接用完整前缀长度。
- 否则查低一分的最早位置，更新距离。
- 每个分数只记录第一次出现。
代码实现
class Solution {
public int longestWPI(int[] hours) {
Map<Integer, Integer> first = new HashMap<>();
int score = 0;
int answer = 0;
for (int idx = 0; idx < hours.length; idx++) {
if (hours[idx] > 8) {
score += 1;
} else {
score -= 1;
}
// 整个前缀已经合法，直接取最长的起点零。
if (score > 0) {
answer = idx + 1;
} else if (first.containsKey(score - 1)) {
answer = Math.max(answer, idx - first.get(score - 1));
}
// 只保留最早位置，给后续右端留下最长区间。
first.putIfAbsent(score, idx);
}
return answer;
}
}
func longestWPI(hours []int) int {
first := make(map[int]int, len(hours))
score := 0
answer := 0
for idx, hour := range hours {
if hour > 8 {
score++
} else {
score--
}
// 整个前缀已经合法，直接取最长的起点零。
if score > 0 {
answer = idx + 1
} else if left, ok := first[score-1]; ok && idx-left > answer {
answer = idx - left
}
// 只保留最早位置，给后续右端留下最长区间。
if _, ok := first[score]; !ok {
first[score] = idx
}
}
return answer
}
复杂度分析
- 时间复杂度：期望 $O(n)$。每一天只更新一次分数，并做常数次哈希表查询和写入。
- 空间复杂度：$O(n)$，前缀分数的最早下标。
关键点总结
[!green]
- 只查低一分的证明依赖每步恰好增加或减少一。
- 记录位置是前缀结束处，答案区间从其下一天开始。
易错点总结
[!yellow]
- 八小时不算劳累，使用大于等于会改变题意。
- 覆盖最早下标会缩短后续区间。
- Go 不检查键是否存在，会把缺失记录的零值当真实下标。
- 前缀分数为零时仍可能存在合法的内部区间，需要继续查询低一分的位置，不能直接判定没有答案。
- 全部天数都不劳累时分数不断下降，低一分尚未出现，答案保持零；全部劳累时完整前缀不断增长，最终取全长。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 525. 连续数组 | 中等 | 同样将两类元素映射成正负贡献，原题要求和为0，本题要求和严格为正。 |
| 962. 最大宽度坡 | 中等 | 同样用单调下降的左端候选配合逆序右端寻找最宽合法区间，前缀和值的比较条件不同。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！