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

难度

• Easy
• Medium
• Hard

思路

将达标日记为 1 ，不达标日记为 -1 ，那么实际要求的，就是和大于 0 的最长区间长度。

在这个问题上找不到正确思路，学习了官解的哈希表解法。

1. 计算前缀和数组，s[0] = 0 ，遍历 i in range(1, n + 1) ，当 hours[i - 1] > 8 时，s[i] = s[i - 1] + 1 ，否则 s[i] = s[i - 1] - 1 。
2. 枚举区间右端点，当 s[right] > 0 ，说明从起始到右端点的和大于 0 ，满足要求，更新 ans 。
3. 当 s[right] < 0 ，我们需要找到一个尽可能小于 right 的下标 left ，且 s[left] 恰好等于 s[right] - 1 ，如果存在，则其是对应于右端点的最长区间的左端点。这一点的证明尚不太理解，但实践验证确实没错。
4. 用哈希表记录每个前缀和首次出现的位置，然后枚举右端点即可。

代码

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        s = [0]
        for hour in hours:
            if hour > 8:
                s.append(s[-1] + 1)
            else:
                s.append(s[-1] - 1)
        last = {}
        for idx, num in enumerate(s):
            if num not in last:
                last[num] = idx
        ans = 0
        for right, num in enumerate(s):
            if num > 0:
                ans = max(ans, right)
            else:
                if num - 1 in last and last[num - 1] < right:
                    ans = max(ans, right - last[num - 1])
        return ans