[LeetCode] 334 | Increasing Triplet Subsequence | Python

---

문제 링크: https://leetcode.com/problems/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.

---

조건

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

---

내 풀이

nums = [2,1,3,2,4]라 할 때, 조건에 해당하는 triple은 (2, 3, 4), (1, 3, 4), (1, 2, 4)가 될 수 있다.

이것을 살펴보면, 2 뒤의 1이 2보다 작기 때문에 triple의 맨 앞을 1로 가져가는 것이 2로 가져가는 것보다 그 경우의 수가 더 많아진다.

이 점을 고려하여 triple의 앞 두 수를 first, second라 정의하고, 이를 무한대로 둔다.

nums의 앞에서부터 차례로 확인한 후 이 숫자가 first보다 작으면 first를 대체하고, first보다 크고 second보다 작으면 second를 대체한다.

만약 first와 second보다 더 크면 문제에서 말하는 조건을 만족하게 되므로 True를 리턴한다.

---

코드

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        first, second = float(inf), float(inf)
        
        for num in nums:
            if num <= first:
                first = num
            elif num <= second:
                second = num
            else:
                return True
        
        return False