456. 132 Pattern

문제 링크 : https://leetcode.com/problems/132-pattern/

주어진 배열 nums가 132패턴을 따르면 true 아니면 False를 반환하는 문제이다.

1,3,2 패턴을 만족하기 위해서는 예를들어 i,j,k가 있으면 i가 작은 수 j에 큰 수가 오면 맨 마지막 숫자k가 i보다는 크고 j보다는 작아야한다.
따라서 nums에서 작은 수, 큰 수를 stack에 저장하여 이를 이용하여 풀 수 있다.

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        stack =[] #pair of i,j
        minn=nums[0]
        for n in nums[1:]:
            while stack and n >= stack[-1][0]:
                stack.pop()
            if stack and n>stack[-1][1]:
                return True
            
            
            stack.append([n,minn])
            minn= min(n,minn)
        return False

22.1230 복습