题目描述
leetcode 中等题
给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。
我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。
所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
请你返回「表现良好时间段」的最大长度。
示例1：
1
2
3
| 输入：hours =
输出：3
解释：最长的表现良好时间段是 。
|
提示1：
1
2
| 1 <= hours.length <= 104
0 <= hours[i] <= 16
|
贪心 + 单调栈
我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。
那么可以将大于 8 小时的天数转化成 $1$ ，否则转换成 $-1$ ，此时 表现良好的时间段 指的就是某段和为正数的子数组，满足条件的最长子数组的长度即为答案。
需要满足子数组和为正数，那么容易想到构造一个原数组的前缀和数组，其中 $preSum[i]$ 表示原数组 $[0…i - 1]$ 的元素和。此时可以通过遍历前缀和数组，对于 $preSum[i]$ 找到一个左边最远的下标 $left$ ，使得满足 $preSum[i] - preSum[left] > 0$ ，此时 $max(i - left)$ 为答案。
对于下标 $i$ 找到左边最远的满足 $preSum[left] < preSum[i]$ 的 $left$ ，一种方法是通过单调栈来实现。
我们维护一个栈，从栈底到栈顶元素单调递减。
考虑顺序遍历，若 $preSum[i] > stk.peek()$，则弹出栈顶最小元素。
- 如果 $preSum[i] > preSum[i + 1]$ ，当前的 $i$ 可能将后续所需要的栈元素弹出，且以后续下标为右端点的区间可能更长，导致结果不正确；
考虑逆序遍历，若 $preSum[i] > stk.peek()$，则弹出栈顶最小元素。
- 如果 $preSum[i - 1] < preSum[i]$ ，虽然当前 $i$ 弹出的元素也会影响到 $i - 1$ ，但是因为如果以 $preSum[i - 1]$ 为右端点能取到一个满足题意的区间时，$preSum[i]$ 也必然能够取到，且更长，所以没必要考虑 $i - 1$ 。
- 如果 $preSum[i - 1] > preSum[i]$，则当前 $i$ 所弹出的元素都是 $i - 1$ 所要弹出的，所以不会影响答案的正确性。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public int longestWPI(int[] hours) {
hours = Arrays.stream(hours).map(i -> i > 8 ? 1 : - 1).toArray();
int n = hours.length;
int[] preSum = new int[n + 1];
for(int i = 1; i <= n; i++){
preSum[i] = preSum[i - 1] + hours[i - 1];
}
Deque<Integer> monoStack = new ArrayDeque<>();
for(int i = 0; i <= n; i++){
if(monoStack.isEmpty() || preSum[monoStack.peek()] > preSum[i]){
monoStack.push(i);
}
}
int ans = 0;
for(int i = n; i >= 1; i--){
int left = -1;
while(!monoStack.isEmpty() && preSum[monoStack.peek()] < preSum[i]){
left = monoStack.pop();
}
ans = left == -1 ? ans : Math.max(ans, i - left);
}
return ans;
}
}
|
贪心 + 哈希表
我们也可以不需要单调栈来实现找到左边最远的满足 $preSum[left] < preSum[i]$ 的 $left$ 。
这是因为前缀和数组满足连续性，也就是如果某个数 $i$ 存在，则 $i - 1$ 也必然存在。
所以对于某个 $preSum[i]$ ，此时左边最远的小于 $preSum[i]$ 的值，就必然是 $preSum[i] - 1$ 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int longestWPI(int[] hours) {
hours = Arrays.stream(hours).map(i -> i > 8 ? 1 : - 1).toArray();
int n = hours.length;
int[] preSum = new int[n + 1];
for(int i = 1; i <= n; i++){
preSum[i] = preSum[i - 1] + hours[i - 1];
}
Map<Integer, Integer> indexMap = new HashMap<>();
int ans = 0;
for(int i = 1; i <= n; i++){
if(preSum[i] > 0){
ans = Math.max(ans, i);
continue;
}
indexMap.putIfAbsent(preSum[i], i);
if(indexMap.get(preSum[i] - 1) != null){
ans = Math.max(ans, i - indexMap.get(preSum[i] - 1));
}
}
return ans;
}
}
|