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

Posted on | In | |

给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。
我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。
所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
请你返回「表现良好时间段」的最大长度。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-well-performing-interval
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
对前缀和的理解还是很模糊。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def longestWPI(self, hours):
        """
        :type hours: List[int]
        :rtype: int
        """
        n = len(hours)
        score = [1 if item > 8 else -1 for item in hours ]

        presum = [0] * ( n + 1 )
        for i in range(1, n+1):
            presum[i] = presum[i-1] + score[i-1]

        index_record = list()
        for i in range(len(presum)):
            if len(index_record) == 0 or presum[i] < presum[index_record[-1]]:
                index_record.append(i)
        result = 0
        for i in range(len(presum) -1 ,-1,-1):
            while len(index_record) and presum[i] - presum[index_record[-1]] > 0 :
                result = max(i - index_record[-1] , result)
                index_record.pop()
        return result