1124. Longest Well Performing Interval (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def longestWPI(self, hours):
        """
        :type hours: List[int]
        :rtype: int
        """
        # hash table
        hours = [1 if x > 8 else -1 for x in hours]
        for i in range(len(hours) - 1):
            hours[i + 1] += hours[i]
        h, result = {}, 0
        for i, num in enumerate(hours):
            if num > 0: 
                result = i + 1
            else:
                if num not in h:
                    h[num] = i
                if num - 1 in h:
                    result = max(result, i - h[num - 1])
        return result
    
        # monostack
        hours = [1 if x > 8 else -1 for x in hours]
        n = len(hours)
        for i in range(n - 1):
            hours[i + 1] += hours[i]
        monostack = [0]
        result = 0
        for i in range(n):
            if hours[i] < hours[monostack[-1]]:
                monostack.append(i)
        for i in range(n - 1, -1, -1):
            if hours[i] > 0:
                if i + 1 >= result:
                    return i + 1
                # result = max(result, i + 1)
            else:
                while monostack and hours[i] > hours[monostack[-1]]:
                    result = max(result, i - monostack.pop())
        return result