LeetCode1124-表现良好的最长时间段

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/longest-well-performing-interval/

中文链接：https://leetcode-cn.com/problems/longest-well-performing-interval/

题目详述

给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。

我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。

所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。

请你返回「表现良好时间段」的最大长度。

示例 1：

1
2
3
输入：hours = [9,9,6,0,6,6,9]
输出：3
解释：最长的表现良好时间段是 [9,9,6]。

提示：

  • 1 <= hours.length <= 10000
  • 0 <= hours[i] <= 16

题目详解

  • 大于 8 的数看作 1，否则看作 -1，问题就转换为了在数组中求最长的区间，它的区间和大于 0。
  • 由区间和可以想到对数组求前缀和，两个前缀和之差就是一个区间和。
  • 要求最长的区间和，可以用一个哈希表存储每个前缀和最早出现的位置。
  • 遍历数组，对于当前前缀和：
    • 如果它大于 0，说明整个前缀和区间满足要求，直接更新结果。
    • 若果它不大于 0，在哈希表中查找比它小一出现的位置，并更新结果。
  • 由于只有当前缀和不大于 0 时才会在哈希表中进行查找，所以实际上只用记录前缀和不大于 0 的位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class LeetCode_01124 {

    public int longestWPI(int[] hours) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        int s = 0;
        for (int i = 0; i < hours.length; ++i) {
            s += hours[i] > 8 ? 1 : -1;
            if (s > 0) {
                res = i + 1;
            } else {
                int b = map.getOrDefault(s - 1, -1);
                if (b != -1) {
                    res = Math.max(res, i - b);
                }
                map.putIfAbsent(s, i);
            }
        }
        return res;
    }
}