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

Difficulty
Medium
Tags
前缀和
单调栈
URL
https://leetcode-cn.com/problems/longest-well-performing-interval/
Star
给你一份工作时间表 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
通过次数14,689提交次数44,913

法1 前缀和 + 单调栈

思路
可以将本题抽象为：
找最大子数组，该子数组内 大于等于 8 的个数 大于小于 8 的个数。
可以可以将 数组中 大于等于8的值 转为 1, 小于等于8的个数转为 -1。此时，问题抽象为：
找最大子数字，该子数组和大于0。
再进一步，求子数字前缀和，问题遍可以转化为
🚔
962. 最大宽度坡
题解
class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        res = 0
        stack = []
        
        # 计算前缀和
        prefix = [0 for _ in range(len(hours)+1)]
        for i in range(1, len(prefix)):
            prefix[i] = (prefix[i-1] + 1) if hours[i-1] > 8 else (prefix[i-1] - 1)
        # 将递减元素下标入栈
        for i in range(0, len(prefix)):
            if len(stack) == 0 or prefix[stack[-1]] > prefix[i]:
                stack.append(i)

        for i in range(len(prefix)-1, -1, -1):
						# 成立的话, (stk[-1], j)是一个候选项
            while stack and prefix[i] > prefix[stack[-1]]:
                res = max(res, i-stack[-1])
                stack.pop()  

        return res