#label: stack diffiuculty: medium

"""
思路：

本题有多种方法，暴力的方法时间复杂度是 O(N**2)，用二分法可以将时间复杂度降为 O(NlogN) ，下面介绍用单调栈可以实现 O(N) 时间复杂度的方法。
其实本题变形后与 962. 最大宽度坡 类似。

以输入样例 hours = [9,9,6,0,6,6,9] 为例，我们将大于 8 小时的一天记为 1 分，小于等于 8 小时的一天记为 −1 分。
那么处理后，我们得到 score = [1, 1, -1, -1, -1, -1, 1]，然后我们对得分数组计算前缀和 presum = [0, 1, 2, 1, 0, -1, -2, -1]。
题目要求返回表现良好时间段的最大长度，即求最长的一段中，得分 1 的个数大于得分 −1 的个数，也就是求 score 数组中最长的一段子数组，其和大于 
0，那么也就是找出前缀和数组 presum 中两个索引 i 和 j，使 j - i 最大，且保证 presum[j] - presum[i] 大于 0。
到此，我们就将这道题转化为，求 presum 数组中的一个最长的上坡，可以用单调栈实现。我们维护一个单调栈，其中存储 presum 中的元素索引，
栈中索引指向的元素严格单调递减，由 presum 数组求得单调栈为 stack = [0, 5, 6]， 其表示元素为 [0, -1, -2]。
然后我们从后往前遍历 presum 数组，与栈顶索引指向元素比较，如果相减结果大于 0，则一直出栈，直到不大于 0 为止，然后更新当前最大宽度。

"""

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        n = len(hours)
        # 大于8小时计1分 小于等于8小时计-1分
        score = [0] * n
        for i in range(n):
            if hours[i] > 8:
                score[i] = 1
            else:
                score[i] = -1
        # 前缀和
        presum = [0] * (n + 1)  #第一个数补0，包含不取的情况
        for i in range(1, n + 1):
            presum[i] = presum[i - 1] + score[i - 1]
        ans = 0
        stack = []
        # 顺序生成单调栈，栈中元素从第一个元素开始严格单调递减，最后一个元素肯定是数组中的最小元素所在位置
        for i in range(n + 1):
            if not stack or presum[stack[-1]] > presum[i]:
                stack.append(i)
        # 倒序扫描数组，求最大长度坡
        i = n
        while i > ans:
            while stack and presum[stack[-1]] < presum[i]:
                ans = max(ans, i - stack[-1])
                stack.pop()
            i -= 1
        return ans
    
