1124-表现良好的最长时间段(Longest Well-Performing Interval)

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

英文原文

We are given hours, a list of the number of hours worked per day for a given employee.

A day is considered to be a tiring day if and only if the number of hours worked is (strictly) greater than 8.

A well-performing interval is an interval of days for which the number of tiring days is strictly larger than the number of non-tiring days.

Return the length of the longest well-performing interval.

Example 1:

Input: hours = [9,9,6,0,6,6,9]
Output: 3
Explanation: The longest well-performing interval is [9,9,6].

Example 2:

Input: hours = [6,6,6]
Output: 0

Constraints:

1 <= hours.length <= 10⁴
0 <= hours[i] <= 16

中文题目

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

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

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

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

示例 1：

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

示例 2：

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

提示：

1 <= hours.length <= 10⁴
0 <= hours[i] <= 16

通过代码

高赞题解

参考链接 :参考1; 参考2;

观察到题目中给出数组中的元素有且只有两种,分别是大于8和小于等于8,而具体的数值没有意义.所以简单起见,我们用1代表大于8的元素,用-1代表小于等于8的元素,得到一个数组[1,1,-1,-1,-1,-1,1]记为arr.
现在题目变成了,我们需要找到一个子列,子列中1的元素数量严格大于-1的元素数量.
继续简化: 也就是需要找到一个子列,子列中所有元素的和大于0.
这时自然可以想到直接暴力遍历所有子列,找到和大于0且长度最大的子列即可.
1. 我们需要的仅仅是子列和,所以这里有一个技巧:
  - i是数组的任意下标,计算arr[0]到arr[ i ]的和
  - 对数组中的每一个下标都计算一次,得到一个新的数组,它被称为前缀和数组
```
arr = [1, 1, -1, -1, -1, -1, 1]
prefixSum = []  # 前缀和数组

cur_sum = 0
for val in arr:
    prefixSum.append(cur_sum)
    cur_sum += val
prefixSum.append(cur_sum)

print(prefixSum)  # [0, 1, 2, 1, 0, -1, -2, -1] 注意这里比arr多了一个元素
```
  - 这时就能很容易找到每一个子列和了,比如我想要arr[2]+arr[3]+…+arr[5]的和直接用prefixSum[6] - prefixSum[2]即可,得到结果是-4.
将任意一个子列表示为 (i, j) ,i和j分别是prefixSum数组中某个元素的下标.
直接暴力遍历每一个(i, j)即可找出答案.
继续优化.首先明确一下我们的目标:找到一个(i,j)使得prefixSum[j] - prefixSum[i] > 0.
1. 按照暴力遍历的思路来看,我们需要在prefixSum数组进行这样的循环:
```
i = 0
j = 0
num = len(prefixSum)
for i in range(num):
    for j in range(i + 1, num):
        # 检查每一对下标看是否符合条件
        if prefixSum[i] < prefixSum[j]:
            res = max(j - i, res)
```
2. 这时观察到,在遍历内层循环j的过程中, 给任意一个i < j1 < j2, 如果prefixSum[i] < prefixSum[j2], 那么(i,j1)一定不会是答案.
  
  也就是说,如果(i, j2)符合条件, 那么它们中间的所有j1都不需要再检查, 所以我们可以从右往左遍历j:
```
i = 0
j = 0
res = 0
num = len(prefixSum)
for i in range(num):
    for j in range(num - 1, i, -1):  # j现在是从7遍历到1
        if prefixSum[i] < prefixSum[j]:
            res = max(j - i, res)
            continue  # 说明此时剩下的(i,j)不是候选项
```
3. 又观察到, 在遍历外层循环i的过程中, 在对于任意的一个i < i1 < j, 如果prefixSum[i1] >= prefixSum[i],那么(i1, j)一定不会是答案.
  
  因为:
  - 如果prefixSum[j] > prefixSum[i1], 那么(i1, j)一定不会是答案,因为(i, j)更长.
  - 如果prefixSum[j] < prefixSum[i1], 那么(i1, j)也一定不会是答案,因为我们要找prefixSum[j] -prefixSum[i1] > 0的(i, j)
  这时我们需要从头遍历一遍prefixSum, 找到一个严格单调递减的数组.
  
  比如当前这个测试用例,只有[0, 5, 6]可能是i的候选项.
```
# prefixSum = [0, 1, 2, 1, 0, -1, -2, -1] 
stk = []
for i in range(len(prefixSum)):
    if len(stk) == 0 or prefixSum[stk[-1]] > prefixSum[i]:
        stk.append(i)  # 因为最终需要的答案是最长距离,需要下标来计算,所以这里存储下标
    print(stk)  # [0, 5, 6]
```
现在问题就变成了,遍历 stk = [0 ,5, 6], 拿到一个i, 再从右向左遍历prefixSum = [0, 1, 2, 1, 0, -1, -2, -1] ,拿到一个j, 检查每一对(i, j)
此时再观察
- 对于一个j, 如果它满足prefixSum[j] > prefixSum[stk[0]], 那么(0, j)是候选项, 但是由于stk是单调递减的,所以prefixSum[j]也是>prefixSum[stk[0 + x]],那么(stk[0 + x], j)也是候选项.
- 对于一个j, 如果它满足prefixSum[j] < prefixSum[stk[0]], 那么(0, j)不是候选项, 但是prefixSum[j]和prefixSum[stk[0 + x]]的大小关系无法判断,所以(stk[0 + x], j)也是候选项.
- 但是如果反过来, 反向遍历stk, 对于一个j 如果它满足prefixSum[j] < prefixSum[stk[-1]], 因为是单调递减的,所以stk中的其他元素都不会再小于prefixSum[j] , 所以j就可以直接被排除掉.
- 再然后, 如果对于一个j 如果它满足prefixSum[j] > prefixSum[stk[-1]], 那么(stk[-1], j)就是候选项,此时再根据7.1, 对于stk[-1]来说, j再继续向左遍历已经没有意义了,所以就可以把stk[-1]排除掉了.而stk[-2]及后面的元素还需要继续判断,但也不必回溯到prefixSum的最右端继续遍历j了.
根据以上思路, 操作刚好契合栈, 所以就用栈stk来存储[0, 5, 6], 得到最终的代码.关键在21到29行
```
def longestWPI(self, hours: List[int]) -> int:
    arr = []
    for val in hours:
        if val > 8:
            arr.append(1)
        else:
            arr.append(-1)

    prefixSum = []  # 前缀和数组
    cur_sum = 0
    for val in arr:
        prefixSum.append(cur_sum)
        cur_sum += val
    prefixSum.append(cur_sum)

    stk = []
    for i in range(len(prefixSum)):
        if len(stk) == 0 or prefixSum[stk[-1]] > prefixSum[i]:
            stk.append(i)  # 因为最终需要的答案是最长距离,需要下标来计算,所以这里存储下标

    res = 0
    # 逆向遍历prefixSum
    for j in range(len(prefixSum) - 1, -1, -1):
        # 成立的话, (stk[-1], j)是一个候选项
        while len(stk) != 0 and prefixSum[j] > prefixSum[stk[-1]]:
            res = max(res, j - stk[-1])
            stk.pop()
    
    return res
```

统计信息

通过次数	提交次数	AC比率
13465	41989	32.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途