1124：表现良好的最长时间段（1908 分）

力扣第 145 场周赛第 3 题

题目

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

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

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

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

示例 1：

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

示例 2：

输入：hours = [6,6,6]
输出：0

提示：

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

分析

数据规模是 10^4，直接暴力会超时。为了方便，可以将大于 8 的位置赋值 1，其它的位置赋值 -1。问题即是求最长的子数组，其和大于 0。

有关子数组的和的问题，首先想到前缀和。得到前缀数组 pre 后，问题即是求最大的 j-i 使得 pre[i] < pre[j]。

现在的问题非常类似 0962 ，用单调栈即可在 O(N) 时间解决。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def longestWPI(self, hours: List[int]) -> int:
	pre = list(accumulate([0]+hours, lambda x, y: x+(1 if y > 8 else -1)))
	stack, n = [], len(pre)
	for i in range(n):
		if not stack or pre[stack[-1]] > pre[i]:
			stack.append(i)
	res = 0
	for j in range(n-1, -1, -1):
		while stack and pre[stack[-1]] < pre[j]:
			res = max(res, j-stack.pop())
	return res

220 ms