难度: Medium
给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。
我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。
所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
请你返回「表现良好时间段」的最大长度。
示例 1：
输入：hours = [9,9,6,0,6,6,9] 输出：3 解释：最长的表现良好时间段是 [9,9,6]。
示例 2：
输入：hours = [6,6,6] 输出：0
提示：
1 <= hours.length <= 1040 <= hours[i] <= 16运行时间: 40 ms
内存: 16.9 MB
class Solution:
def longestWPI(self, hours: List[int]) -> int:
sum=0
n=len(hours)
for i in range(n):
if hours[i]>8:
hours[i]=1
else:
hours[i]=-1
sum+=hours[i]
if sum>0:
return n
sum=[0]*n
sum[0]=hours[0]
for i in range(n):
sum[i]=sum[i-1]+hours[i]
ans=0
aim=1
hash_table={0:-1}
for i in range(n):
if hash_table.get(sum[i]-aim)is not None:
ans=max(ans,i-hash_table.get(sum[i]-aim))
if hash_table.get(sum[i])is None:
hash_table[sum[i]]=i
return ans
这个题解首先将工作时间hours数组转化为劳累天数标记为1，不劳累天数标记为-1的形式。接着，计算这个转化后的数组的前缀和。如果前缀和大于0，则整个数组都是一个表现良好的时间段，直接返回数组长度。若不是，利用哈希表记录前缀和的最早出现位置。通过检查当前前缀和减去一个目标值(aim = 1)是否存在于哈希表中，来找到最长的表现良好时间段，即找到最早使得累积和大于1的子数组。通过这种方式，我们可以在一次遍历中找到最长的满足条件的子数组长度。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def longestWPI(self, hours: List[int]) -> int:
sum = 0
n = len(hours)
# 将每个工作时长转换为1或-1
for i in range(n):
if hours[i] > 8:
hours[i] = 1
else:
hours[i] = -1
sum += hours[i]
# 如果所有天数加起来劳累的天数更多
if sum > 0:
return n
sum = [0] * n
sum[0] = hours[0]
for i in range(1, n):
sum[i] = sum[i-1] + hours[i]
ans = 0
aim = 1
hash_table = {0: -1}
# 使用哈希表找到最长的表现良好时间段
for i in range(n):
if hash_table.get(sum[i] - aim) is not None:
ans = max(ans, i - hash_table.get(sum[i] - aim))
if hash_table.get(sum[i]) is None:
hash_table[sum[i]] = i
return ans
在这个问题中，我们的目标是找到最长的时间段，其中劳累的天数（表示为+1）超过不劳累的天数（表示为-1）。将此问题转化为寻找一个子数组的前缀和大于0的问题。具体来说，如果我们在位置j的前缀和减去一个之前在位置i的前缀和等于1（即sum[j] - sum[i] = 1），这意味着从i+1到j的子数组中，劳累的天数比不劳累的天数多一个，满足题目要求。因此，我们查找前缀和为当前前缀和减1的最早出现位置，这样的操作可以有效地帮助我们定位到满足条件的子数组，进而计算出这个子数组的长度。
哈希表中初始化{0: -1}是为了处理从数组开始到某个位置j的前缀和为1的情形。在这种情况下，我们可以认为从位置0开始到位置j的子数组（实际上是从位置1到j，因为数组索引从0开始）满足题目条件。将0的位置设为-1意味着我们可以用同一种逻辑处理这种情形和其他情形，即如果sum[j] - 1 = 0（即sum[j] = 1），我们可以直接使用j - (-1) = j + 1来计算子数组的长度。这样的初始化简化了代码逻辑，避免了对数组开头的特殊处理。