题目描述
思路解析动画文字版
两套判定:score>0 时整段 [0..i] 合格;score≤0 时去哈希表查 first[score−1] 配出区间。哈希表只记每个前缀和最早的下标。下面逐天演示。
开始前:前缀和 score = 0,答案 best = 0,哈希表 first 还是空的。指针 i 从下标 0 出发。
指针 i 走到下标 0:工作 6 小时 ≤ 8 → 非劳累日,记 −1。
score = -1 ≤ 0,去查更早出现过 -2 的位置,但表里还没有,所以这一步没找到合格区间,best 仍是 0。
前缀和 -1 还是第一次见,把它的最早下标 0 记进哈希表(只记最早一次,区间才最长)。
指针 i 走到下标 1:工作 6 小时 ≤ 8 → 非劳累日,记 −1。
score = -2 ≤ 0,去查更早出现过 -3 的位置,但表里还没有,所以这一步没找到合格区间,best 仍是 0。
前缀和 -2 还是第一次见,把它的最早下标 1 记进哈希表(只记最早一次,区间才最长)。
指针 i 走到下标 2:工作 6 小时 ≤ 8 → 非劳累日,记 −1。
score = -3 ≤ 0,去查更早出现过 -4 的位置,但表里还没有,所以这一步没找到合格区间,best 仍是 0。
前缀和 -3 还是第一次见,把它的最早下标 2 记进哈希表(只记最早一次,区间才最长)。
指针 i 走到下标 3:工作 9 小时 > 8 → 劳累日,记 +1。
score = -2 ≤ 0,去查更早出现过 -3 的位置:first[-3] = 2。那么从下标 3 到 3 这段分数正好 > 0,长度 1。best 刷新为 1。
前缀和 -2 之前已经出现过,哈希表里保留它最早的下标 1,不覆盖——这样配出的区间才最长。
指针 i 走到下标 4:工作 9 小时 > 8 → 劳累日,记 +1。
score = -1 ≤ 0,去查更早出现过 -2 的位置:first[-2] = 1。那么从下标 2 到 4 这段分数正好 > 0,长度 3。best 刷新为 3。
前缀和 -1 之前已经出现过,哈希表里保留它最早的下标 0,不覆盖——这样配出的区间才最长。
指针 i 走到下标 5:工作 9 小时 > 8 → 劳累日,记 +1。
score = 0 ≤ 0,去查更早出现过 -1 的位置:first[-1] = 0。那么从下标 1 到 5 这段分数正好 > 0,长度 5。best 刷新为 5。
前缀和 0 还是第一次见,把它的最早下标 5 记进哈希表(只记最早一次,区间才最长)。
指针 i 走到下标 6:工作 6 小时 ≤ 8 → 非劳累日,记 −1。
score = -1 ≤ 0,去查更早出现过 -2 的位置:first[-2] = 1。那么从下标 2 到 6 这段分数正好 > 0,长度 5。没超过现有 best=5。
前缀和 -1 之前已经出现过,哈希表里保留它最早的下标 0,不覆盖——这样配出的区间才最长。
指针 i 走到下标 7:工作 6 小时 ≤ 8 → 非劳累日,记 −1。
score = -2 ≤ 0,去查更早出现过 -3 的位置:first[-3] = 2。那么从下标 3 到 7 这段分数正好 > 0,长度 5。没超过现有 best=5。
前缀和 -2 之前已经出现过,哈希表里保留它最早的下标 1,不覆盖——这样配出的区间才最长。
指针 i 走到下标 8:工作 6 小时 ≤ 8 → 非劳累日,记 −1。
score = -3 ≤ 0,去查更早出现过 -4 的位置,但表里还没有,所以这一步没找到合格区间,best 仍是 5。
前缀和 -3 之前已经出现过,哈希表里保留它最早的下标 2,不覆盖——这样配出的区间才最长。
扫描结束。整趟里最长的「累 > 不累」区间是高亮的下标 1 到 5(共 5 天),best=5 就是答案。
三个高频追问:±1 转化的依据、哈希只记最早、两个分支为何分开。
参考代码
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 best复杂度
- 时间:O(n),指针 i 把数组扫一遍,每步哈希查/存都是 O(1)
- 空间:O(n),哈希表 first 最多存 n 个不同的前缀和
易错点
面试追问把动画讲成自己的话
追问为什么把 >8 小时记 +1、否则记 −1 就能解?
追问哈希表为什么只存每个前缀和第一次出现的下标?
追问score > 0 和 score ≤ 0 两个分支能合并吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
统计「优美子数组」
LeetCode 1248 · 中等 · 沿着 前缀和套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题