表现良好的最长时间段（LeetCode）

题目

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

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

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

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

解题

"""
时间复杂度: O(n)，因为我们只遍历一次数组。
空间复杂度: O(n)，用于存储前缀和及其对应的索引。
"""def longestWPI(hours):prefix_sum = 0prefix_map = {}max_length = 0for i, h in enumerate(hours):# 如果 h > 8，prefix_sum +1; 否则 -1prefix_sum += 1 if h > 8 else -1if prefix_sum > 0:# 如果前缀和大于0，说明从开始到i的子数组都满足条件max_length = i + 1else:# 检查是否存在 prefix_sum - 1，如果存在则说明有符合条件的子数组if prefix_sum - 1 in prefix_map:max_length = max(max_length, i - prefix_map[prefix_sum - 1])# 如果 prefix_sum 不在哈希表中，记录下它第一次出现的索引if prefix_sum not in prefix_map:prefix_map[prefix_sum] = ireturn max_length# 示例 1
hours = [9, 9, 6, 0, 6, 6, 9]
print(longestWPI(hours))  # 输出: 3