leetcode
leetcode 1051 ~ 1100
表现良好的最长时间段

表现良好的最长时间段

难度:

标签:

题目描述

代码结果

运行时间: 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)是否存在于哈希表中,这样的操作逻辑是基于什么考虑?
在这个问题中,我们的目标是找到最长的时间段,其中劳累的天数(表示为+1)超过不劳累的天数(表示为-1)。将此问题转化为寻找一个子数组的前缀和大于0的问题。具体来说,如果我们在位置j的前缀和减去一个之前在位置i的前缀和等于1(即sum[j] - sum[i] = 1),这意味着从i+1到j的子数组中,劳累的天数比不劳累的天数多一个,满足题目要求。因此,我们查找前缀和为当前前缀和减1的最早出现位置,这样的操作可以有效地帮助我们定位到满足条件的子数组,进而计算出这个子数组的长度。
🦆
哈希表中初始化{0: -1}这一步操作是基于什么考虑?这样的初始化有什么特别的意义或作用?
哈希表中初始化{0: -1}是为了处理从数组开始到某个位置j的前缀和为1的情形。在这种情况下,我们可以认为从位置0开始到位置j的子数组(实际上是从位置1到j,因为数组索引从0开始)满足题目条件。将0的位置设为-1意味着我们可以用同一种逻辑处理这种情形和其他情形,即如果sum[j] - 1 = 0(即sum[j] = 1),我们可以直接使用j - (-1) = j + 1来计算子数组的长度。这样的初始化简化了代码逻辑,避免了对数组开头的特殊处理。

相关问题