1124.表现良好的最长时间段

1、题干

给你一份工作时间表 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

2、思路-前缀和+哈希表

• 计算 hours 的前缀和数组 sums，当 hours[i] 大于 8 时前缀和 +1 否则 -1
• 将 sums[i] 与 i 分别作为键值存入哈希表 map；为保证结果时段最大，仅当哈希表中不存在 sums[i] 时才存入该键值对
• 如果 sums[i] 大于 0，则区间 [0,i] 可能是最长时段
• 如果 sums[i] 小于等于 0，则区间 [map.get(sums[i] - 1),i) 也可能是最长时段
• 所有备选时段长度的最大值即所求的最长时段

这题的前缀和在整数范围上具有连续性，所以能用哈希表

3、代码

function longestWPI(hours: number[]): number {
    const sums = hours.map(() => 0);
    const map = new Map();

    let ans = 0;
    for (let i = 0; i < hours.length; i++) {
        sums[i] = (sums[i - 1] || 0) + (hours[i] > 8 ? 1 : -1);
        if (sums[i] > 0) ans = Math.max(ans, i + 1);
        else {
            if (map.has(sums[i] - 1)) ans = Math.max(ans, i - map.get(sums[i] - 1));
        }

        if (!map.has(sums[i])) map.set(sums[i], i);
    }

    return ans;
};

4、复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

5、执行结果

6、前缀和+栈

这个思路是我能写出来的吗

function longestWPI(hours: number[]): number {
    const sums = hours.map(() => 0);
    const minStack = [0];

    let ans = 0;
    for (let i = 0; i < hours.length; i++) {
        sums[i] = (sums[i - 1] || 0) + (hours[i] > 8 ? 1 : -1);
        if (sums[i] > 0) ans = Math.max(ans, i + 1);
        if (sums[i] < sums[minStack.at(-1)]) minStack.push(i);
    }

    for (let i = hours.length - 1; i > -1; i--) {
        while (sums[minStack.at(-1)] < sums[i]) {
            const l = minStack.pop();
            ans = Math.max(ans, i - l);
        }
    }

    return ans;
};