Leetcode 334. Increasing Triplet Subsequence

문제

Given an integer array nums, 
return true if there exists a triple of indices (i, j, k) 
such that i < j < k and nums[i] < nums[j] < nums[k]. 
If no such indices exists, return false.

정수 배열 nums가 주어집니다.
배열의 index 인 i, j, k 에 대해
i < j < k 인 경우 nums[i] < nums[j] < nums[k] 가 성립하는 경우가 존재하는지
boolean 자료형으로 리턴하시오.

예시

Input: nums = [1,2,3,4,5]
Output: true

Input: nums = [5,4,3,2,1]
Output: false

제한

• $1 <= nums.length <= 5 * 10^5$
• $-2^{31} <= nums[i] <= 2^{31} - 1$

풀이법

• 특정 인덱스 x에 대해 자신의 앞에 나란히 증가하는 2개의 수가 있으면 True를 리턴하게 됩니다.
• 이를 확인하기 위해 앞의 두 수를 저장할수 있는 변수 a, b를 만듭니다. ( a < b )
  • 두 변수는 초기값으로 None 을 가집니다.

a	b
None	None

0. nums의 for loop를 돌며 개별값 v에 대해 아래 과정을 반복합니다.
1. a와 b 둘중 하나라도 값이 None일 경우 먼저 이들을 채워야 합니다.
   • a가 None일 경우, 바로 a를 v로 채웁니다.
   • b가 None일 경우 v값이 a보다 크면 b에 채우고, 그렇지 않을 경우 a를 v로 바꿉니다.
2. a, b값이 채워졌을 경우 아래를 반복합니다.
   2-1. v값이 a보다 작을경우 a를 v로 바꿉니다.
   2-2. v값이 b보다 작고 a보다 클 경우
   2-3. v값이 b보다 클 경우 조건을 성립하는 세 숫자가 존재하기에 True를 리턴합니다.

만약 for loop를 전부 돌때까지 True를 리턴하지 않을 경우 False를 리턴하게 됩니다.

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        a, b = None, None

        for i, v in enumerate(nums):

            if a == None:
                a = v
                continue

            if b == None and a < v:
                b = v
                continue
            elif b == None and a >= v:
                a = v
                continue

            if v < a:
                a = v
            elif v < b and v > a:
                b = v
            elif v > b:
                return True

        return False