What is the key approach for solving Longest Well-Performing Interval?

The solution involves converting hours worked into +1/-1 values and finding the longest subarray with a positive sum using prefix sums and hash lookups.

How does the prefix sum technique apply to this problem?

The prefix sum technique helps efficiently track the cumulative sum as you iterate, allowing you to identify the longest well-performing subarray by comparing prefix sums at different indices.

What are common mistakes when solving the Longest Well-Performing Interval?

Common mistakes include not correctly converting the array into +1/-1 values or failing to utilize the prefix sum approach effectively.

How does hash map improve the performance of the solution?

Hash maps allow you to quickly check for previously seen prefix sums, enabling constant-time lookup and reducing the time complexity to O(n).

What other data structures can be used for this problem?

While hash maps are optimal, a stack-based approach can also be used to track prefix sums and manage subarrays, but it may be less efficient.

#1124

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

表现良好的最长时间段

给你一份工作时间表 hours ，上面记录着某一位员工每天的工作小时数。我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格大于「不劳累的天数」。请你返回「表现良好时间段」的最大长度。示例…

数组哈希表栈单调栈前缀和

题目描述

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

lightbulb

解题思路

方法一：前缀和 + 哈希表

我们可以利用前缀和的思想，维护一个变量 $s$ ，表示从下标 $0$ 到当前下标的这一段，「劳累的天数」与「不劳累的天数」的差值。如果 $s$ 大于 $0$ ，说明从下标 $0$ 到当前下标的这一段，满足「表现良好的时间段」。另外，用哈希表 $pos$ 记录每个 $s$ 第一次出现的下标。

接下来，我们遍历数组 hours，对于每个下标 $i$ ：

如果 $hours[i] \gt 8$ ，我们就让 $s$ 加 $1$ ，否则减 $1$ 。
如果 $s$ 大于 $0$ ，说明从下标 $0$ 到当前下标的这一段，满足「表现良好的时间段」，我们更新结果 $ans = i + 1$ 。否则，如果 $s - 1$ 在哈希表 $pos$ 中，记 $j = pos[s - 1]$ ，说明从下标 $j + 1$ 到当前下标 $i$ 的这一段，满足「表现良好的时间段」，我们更新结果 $ans = \max(ans, i - j)$ 。
然后，如果 $s$ 不在哈希表 $pos$ 中，我们就记录 $pos[s] = i$ 。

遍历结束后，返回答案即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 hours 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        ans = s = 0
        pos = {}
        for i, x in enumerate(hours):
            s += 1 if x > 8 else -1
            if s > 0:
                ans = i + 1
            elif s - 1 in pos:
                ans = max(ans, i - pos[s - 1])
            if s not in pos:
                pos[s] = i
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n), where n is the length of the hours array. The space complexity is O(n) due to the storage of prefix sums in the hash map.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate effectively convert the problem into an array of +1/-1 values?
question_mark
Does the candidate demonstrate understanding of prefix sum and hash map techniques?
question_mark
Is the candidate able to optimize the solution by tracking previous sums and finding the longest subarray?

warning

常见陷阱

外企场景

error
Misunderstanding the conversion to +1/-1 for tiring and non-tiring days.
error
Overcomplicating the solution without utilizing the prefix sum approach and hash map efficiently.
error
Missing the fact that the problem requires finding a subarray with a positive sum rather than simply counting tiring days.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handling edge cases where there are no tiring days.
arrow_right_alt
Exploring variations where you are asked to find the shortest subarray with a positive sum.
arrow_right_alt
Solving the problem with a different data structure like a stack to manage sums.

help

常见问题

外企场景

继续练习

#496 下一个更大元素 I #1130 叶值的最小代价生成树 #1074 元素和为目标值的子矩阵数量