表现良好的最长时间段
难度:
标签:
题目描述
代码结果
运行时间: 40 ms, 内存: 16.9 MB
/*
* 思路:
* 使用Java Stream来处理数组。
* 虽然Java Stream不太适合处理带有复杂逻辑的算法问题,但我们可以通过使用IntStream进行基本的转换。
* 然后再使用常规方法处理前缀和与哈希表。
*/
import java.util.HashMap;
import java.util.stream.IntStream;
public class Solution {
public int longestWPI(int[] hours) {
int[] prefixSum = new int[hours.length + 1];
IntStream.range(0, hours.length).forEach(i -> prefixSum[i + 1] = prefixSum[i] + (hours[i] > 8 ? 1 : -1));
HashMap<Integer, Integer> map = new HashMap<>();
final int[] maxLen = {0};
IntStream.range(0, prefixSum.length).forEach(i -> {
if (prefixSum[i] > 0) {
maxLen[0] = i;
} else {
map.putIfAbsent(prefixSum[i], i);
if (map.containsKey(prefixSum[i] - 1)) {
maxLen[0] = Math.max(maxLen[0], i - map.get(prefixSum[i] - 1));
}
}
});
return maxLen[0];
}
}
解释
方法:
这个题解首先将工作时间hours数组转化为劳累天数标记为1,不劳累天数标记为-1的形式。接着,计算这个转化后的数组的前缀和。如果前缀和大于0,则整个数组都是一个表现良好的时间段,直接返回数组长度。若不是,利用哈希表记录前缀和的最早出现位置。通过检查当前前缀和减去一个目标值(aim = 1)是否存在于哈希表中,来找到最长的表现良好时间段,即找到最早使得累积和大于1的子数组。通过这种方式,我们可以在一次遍历中找到最长的满足条件的子数组长度。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在使用哈希表记录前缀和及其最早出现位置时,为什么要查找当前前缀和减去1(aim = 1)是否存在于哈希表中,这样的操作逻辑是基于什么考虑?
▷🦆
哈希表中初始化{0: -1}这一步操作是基于什么考虑?这样的初始化有什么特别的意义或作用?
▷