456. 132 Pattern

link

Count min for nums[:i] from the left. Use stack from the right.

Try to find the max in the middle.

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        # min_list[i] = min(nums[0], ..., nums[i])
        min_list = list(accumulate(nums, min))

        stack = []

        for i in range(len(nums)-1, -1, -1):
            current = float('-inf')
            # mono decreasing stack
            while stack and stack[-1] < nums[i]:
                current = stack.pop()
            if current > min_list[i]:
                return True
            
            stack.append(nums[i])

        # similar solution
        # for i in range(len(nums)-1, -1, -1):
        #     if nums[i] > min_list[i]:
        #         while stack and stack[-1] <= min_list[i]:
        #             stack.pop()
        #         if stack and stack[-1] < nums[i]:
        #             return True
                
        #         stack.append(nums[i])

        return False