外贸网站建设海外推广,广州抖音seo价格,永久免费crm软件哪个好,网站管理主要包括哪些内容题目 给你一份工作时间表 hours#xff0c;上面记录着某一位员工每天的工作小时数。 我们认为当员工一天中的工作小时数大于 8 小时的时候#xff0c;那么这一天就是「劳累的一天」。 所谓「表现良好的时间段」#xff0c;意味在这段时间内#xff0c;「劳累的天数」是严格…题目 给你一份工作时间表 hours上面记录着某一位员工每天的工作小时数。 我们认为当员工一天中的工作小时数大于 8 小时的时候那么这一天就是「劳累的一天」。 所谓「表现良好的时间段」意味在这段时间内「劳累的天数」是严格 大于「不劳累的天数」。 请你返回「表现良好时间段」的最大长度。 解题 时间复杂度: O(n)因为我们只遍历一次数组。
空间复杂度: O(n)用于存储前缀和及其对应的索引。
def longestWPI(hours):prefix_sum 0prefix_map {}max_length 0for i, h in enumerate(hours):# 如果 h 8prefix_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
