LeetCode 1124. 表现良好的最长时间段

2023-01-18 HGNULB 约 10 分钟

文章信息 7 个分类 5 个标签

分类

题目描述

✅ 1124. 表现良好的最长时间段

题意分析

题目定义「劳累的一天」为工作时长严格大于 8 小时，而「表现良好的时间段」要求这一段连续日子里劳累天数严格多于不劳累天数，要求返回最长这样一段的长度。注意判定条件只关心两类天数的多少关系，具体工作了 9 小时还是 16 小时完全不影响结果，这是一个强烈的信号：原始数值可以被压缩成只有两种取值。

把每天映射成 +1 或 -1 之后，「劳累天数 > 不劳累天数」就等价于「这一段的和严格大于 0」。求「和大于 0 的最长连续子数组」，天然应该用前缀和把区间条件改写成两个端点之间的条件，问题就变成：找一对下标 i < j，使得 pre[j] - pre[i] > 0 且 j - i 最大。

约束里数组长度上限是 10^4，看似 $O(n^2)$ 的双重枚举也能勉强通过，但真正值得注意的是另一条隐含性质：相邻两个前缀和的差恰好是 ±1，也就是前缀和序列是一条每步只走一格的折线。这条性质是本题能做到线性的全部理由，也是它区别于一般「和大于 K」问题的地方。

边界上要想清楚三种：整个数组都不劳累时答案是 0，必须允许返回 0 而不是返回某个下标差；整个数组都劳累时答案是数组长度，说明从下标 0 开始的整段必须能被取到；只有一天时答案要么是 1 要么是 0，不能出现负数长度。

解法：前缀和 + 最早位置

核心思路

暴力做法是枚举所有左右端点对，用前缀和 $O(1)$ 求出区间和判断是否为正，取最长的那一段，复杂度 $O(n^2)$。瓶颈很清楚：对每个右端点 j，我们其实只想知道「在所有满足 pre[i] < pre[j] 的 i 里，最小的那个 i 是谁」，而暴力做法却把所有 i 都扫了一遍。

关键观察是前缀和每步只变化 1 这条性质。既然折线不能跳跃，那么如果存在某个更早的位置 i 满足 pre[i] ≤ pre[j] - 2，那么从这个 i 走到 j 的路上，前缀和必然连续地经过 pre[j] - 1 这个值，也就是说值为 pre[j] - 1 的位置一定出现得比 i 还早或者一样早。因此「找最小的 i 使 pre[i] < pre[j]」可以直接简化成「找值恰好等于 pre[j] - 1 的最早位置」，不需要考虑更小的值。

于是维护的不变量是：一个哈希表 first，first[s] 表示前缀和第一次取到值 s 的下标；扫描过程中只在某个值第一次出现时写入，之后永不更新。这样每个右端点只需要一次哈希查询就能拿到最优左端点。

还剩一种情况需要单独处理：当 pre[j] 本身已经大于 0 时，从数组开头到 j 的整段就已经满足条件，长度是 j + 1，这比任何以中间某点为左端点的区间都长。把这一条单列出来，就不必为「前缀和为 0 的虚拟起点」在哈希表里预置一项，两种情况互斥且合起来覆盖了全部可能。

解题步骤

第一步，初始化哈希表 first、running 前缀分数 score = 0、答案 answer = 0。answer 初值取 0 而不是取 -1 或 Integer.MIN_VALUE，是因为题目允许「不存在这样的时间段」时返回 0，用 0 兜底可以省掉最后的判空。

第二步，从左到右扫描，遇到大于 8 的小时数就把 score 加一，否则减一。这里必须是严格大于 8，恰好等于 8 小时按题意不算劳累；把条件写成大于等于 8 会把正常上班日误判成劳累日。

第三步，先判断 score > 0。成立时直接把 answer 设为 idx + 1，而不是取 max，原因是 idx 单调递增，后面若再次进入这个分支得到的长度必然更大，赋值和取最大值等价，写赋值更能表达「整段前缀都合法」这个含义。

第四步，score ≤ 0 时才去查 first[score - 1]。之所以只在这个分支查，是因为 score > 0 的情况已经拿到了以 0 为左端点的最长解，不可能有更优；而 score ≤ 0 时 score - 1 必然是负数，这个键要么已经在表里，要么整个前缀里根本没出现过更低的值。命中时用 idx - first[score - 1] 更新答案，注意这个差值就是区间长度：左端点是 first 记录的位置的下一天，右端点是 idx，两端相减恰好等于天数。

第五步，本轮结束时用「不存在才写入」的方式记录 first[score] = idx。必须是 putIfAbsent 语义，因为我们要的是最早位置，覆盖写入会让区间被人为缩短。同时这一步放在查询之后，保证查的永远是严格更早的位置。

以 hours = [9,9,6,0,6,6,9] 走一遍：idx 0 时 hour 9 > 8，score 变 1，大于 0，answer = 1，first 记下 {1:0}；idx 1 时 score 变 2，大于 0，answer = 2，first 补上 {2:1}；idx 2 时 hour 6，score 回到 1，仍大于 0，answer = 3，值 1 已存在故不覆盖；idx 3 时 score 变 0，不大于 0，查 first[-1] 未命中，写入 {0:3}；idx 4 时 score 变 -1，查 first[-2] 未命中，写入 {-1:4}；idx 5 时 score 变 -2，查 first[-3] 未命中，写入 {-2:5}；idx 6 时 hour 9，score 回到 -1，查 first[-2] 命中值 5，得到长度 6 - 5 = 1，不足以更新 answer，且值 -1 已存在不覆盖。最终返回 3，对应前三天 [9,9,6] 里两天劳累一天不劳累，和为 +1 大于 0，确实是最长的一段。

代码实现

class Solution {
    // 若当前前缀和 score > 0，从 0 到当前位置整个区间已经满足要求。
    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 {
    // 若当前前缀和 score > 0，从 0 到当前位置整个区间已经满足要求。
    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)$，其中 n 表示数组长度。每个下标只被扫描一次，循环体内只有一次哈希查询和至多一次哈希写入，均摊都是常数时间。

空间复杂度：$O(n)$，哈希表最多存下 n 个不同的前缀和取值（前缀和范围是 -n 到 n，但实际写入次数不超过 n 次），除此之外只用了两个整型变量。

关键点总结

布尔式的计数比较题一律先做 ±1 映射：只要判定条件是「A 类个数多于 B 类个数」，就把 A 记 +1、B 记 -1，问题立刻退化成「区间和大于 0」，前缀和的全套工具随即可用。

前缀和序列每步只变化 1 是本题的题眼。正因为折线连续不跳跃，「找第一个比当前值小的位置」才能被简化成「找恰好小 1 的那个值的最早位置」，从 $O(n^2)$ 降到 $O(n)$。这条性质在所有 ±1 计数题里都成立，值得记牢。

哈希表记录「首次出现位置」是求最长区间的标配，与之对偶的是求「区间个数」时记录出现次数、求「最短区间」时记录最近位置。三种题型用同一张表但更新策略完全不同，要按目标选。

面试视角上，面试官通常会先接受你的 $O(n^2)$ 前缀和写法，然后追问能不能做到线性。此时正确的回答路径是先指出「值域连续变化」这个结构性质，再由它推出只查 score - 1 就够，而不是直接背出结论。能补充说明单调栈解法也能做到线性、但常数和代码量都更大，会是加分项。

score > 0 单独成一个分支，本质上等价于在哈希表里预置 first[0] = -1，两种写法可以互相转换。理解它们的等价性，能避免在同类题里纠结「要不要预置初始前缀和」这个反复出现的坑。

易错点总结

错误写法：把劳累判定写成 hours[idx] >= 8 → 对用例 [8,8,8]，三天都被当成劳累日，score 走到 3 并返回 3，而正确答案是 0，因为恰好 8 小时不算劳累。

错误写法：用 first.put(score, idx) 每次都覆盖 → 对用例 [9,6,6,6,9,9,9]，值为 -1 的最早位置本应是下标 1，被后续覆盖成更靠右的位置，最终区间被截短，返回值小于正确答案。

错误写法：查询和写入顺序颠倒，先写 first[score] 再查 first[score - 1] → 虽然键不同不会自查自己，但如果同时把 score > 0 分支也改成走哈希，就会出现用当前下标减自己得到 0 的无效更新，掩盖真正的答案。

错误写法：把 else if 写成独立的 if，score > 0 时也去查 first[score - 1] → 对用例 [9,9,9]，score 为 1 时查到 first[0] 不存在还好，但 score 为 2 时查到 first[1] = 0，得到长度 1 并用 Math.max 保住了 3，看似没错；一旦答案更新写成直接赋值而非取最大，就会把 3 覆盖成 1。

错误写法：score > 0 分支里写成 answer = Math.max(answer, idx) 漏掉加一 → 对用例 [9]，score 为 1，answer 被设成 0，返回 0，而正确答案是 1。

错误写法：命中哈希时用 idx - first.get(score - 1) + 1 多算一天 → 对用例 [9,6,6,6,9,9,9]，区间长度被整体放大一位，返回的结果超过真实的表现良好时间段长度。

错误写法：在循环外预置 first.put(0, -1) 的同时又保留 score > 0 的赋值分支，且把赋值分支放在 else 里 → 对用例 [9,9]，score 为 1 时走进哈希分支查 first[0] = -1 得到长度 1，永远走不到长度 2 的赋值分支，返回 1 而不是 2。

错误写法：answer 初始化为 Integer.MIN_VALUE 或 -1 → 对用例 [6,6,6]，全程没有任何分支更新答案，直接把初值返回出去，返回负数而不是题目要求的 0。

错误写法：Go 里写成 left := first[score-1] 不接收 ok 直接使用 → 键不存在时 map 返回零值 0，被当成「值为 score-1 的位置在下标 0」，对用例 [6,6,9,9] 会凭空造出一段并返回错误的长度。

错误写法：为了「省空间」把哈希表换成长度为 n 的数组并用 score 直接当下标 → score 可以取到负值，对用例 [6,6,6] 立刻数组越界；即使做了偏移，也要偏移 n 且数组开到 2n + 1，反而不如哈希表清晰。

相似题目

题目	难度	考察点
525. 连续数组	中等	同样 ±1 映射，但目标是和恰好为 0，查的是相同值的最早位置
560. 和为 K 的子数组	中等	求个数而非长度，哈希表存的是前缀和出现次数
325. 和等于 k 的最长子数组长度	中等	值任意不再只差 1，只能查等于 pre-k 的最早位置
974. 和可被 K 整除的子数组	中等	前缀和取模后分桶，需处理负数取模
523. 连续的子数组和	中等	同余判定之外还附加了子数组长度至少为 2 的限制
930. 和相同的二元子数组	中等	0/1 数组求恰好为 goal 的个数，可用两次滑窗相减替代哈希
862. 和至少为 K 的最短子数组	困难	目标改为最短，前缀和不再连续变化，需要单调队列
53. 最大子数组和	中等	求和的最大值而非满足条件的最长长度，用 Kadane 而非哈希
918. 环形子数组的最大和	中等	数组首尾相接，需拆成普通最大和与总和减最小和两种情况
1004. 最大连续1的个数 III	中等	限制是翻转次数上界，条件单调因此滑动窗口可直接适用
84. 柱状图中最大的矩形	困难	本题单调栈解法的原型，栈中存的是候选左端点下标