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

给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。

我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。

所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。

请你返回「表现良好时间段」的最大长度。

示例 1：

输入：hours = [9,9,6,0,6,6,9]
输出：3
解释：最长的表现良好时间段是 [9,9,6]。

提示：

• 1 <= hours.length <= 10000
• 0 <= hours[i] <= 16

栈 数组 中等

像个困难题

代码

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        n = len(hours)
        preSum = [0] * (n+1)
        for i in range(1,n+1):
            preSum[i] = preSum[i-1] + (1 if hours[i-1] > 8 else -1)
        # preSum = preSum[1:]

        stk = []
        for i in range(len(preSum)):
            if not stk or preSum[stk[-1]] > preSum[i]:
                stk.append(i)  # 因为最终需要的答案是最长距离,需要下标来计算,所以这里存储下标

        res = 0
        # 逆向遍历preSum
        for j in range(len(preSum) - 1, -1, -1):
            # 成立的话, (stk[-1], j)是一个候选项
            while len(stk) != 0 and preSum[j] > preSum[stk[-1]]:
                res = max(res, j - stk[-1])
                stk.pop()
        
        return res