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.

Example 1:

Input: nums = [1,2,3,4,5]
Output: true
Explanation: Any triplet where i < j < k is valid.
Example 2:

Input: nums = [5,4,3,2,1]
Output: false
Explanation: No triplet exists.
Example 3:

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

전혀 좋지 않았던 내 풀이시도. 투포인터를 이용하려고 했지만 결국 막혔다.

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        left, right = 0, len(nums) - 1
        output = []

        while left < right:
            if nums[left] < nums[right]:
                output.append(nums[right])
                left += 1
        
            if nums[left] > nums[right]:
                output.append(nums[left])
                right -= 1

            # put the elment of the list nums that is in the middle position of the list into ouput?
            # output is constrained to have three elements
        
        if output[0] < output[1] < ouput[2]:
            True
        else:
            False

모범답안은 다음과 같다

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        first = second = float('inf')
        
        for num in nums:
            if num <= first:
                first = num  # smallest so far
            elif num <= second:
                second = num  # second smallest so far
            else:
                # If we find a number greater than both first and second,
                # we have an increasing triplet
                return True
        
        return False  # no increasing triplet found

가장 작은 숫자(=first)와 그 다음 작은 숫자(=second)를 설정하는 것에서부터 아이디어가 시작하는데, 최초 initialization은 float('inf') 설정한다는 아이디어가 꽤나 낯설면서도 신기했다. 이게 이렇게도 할 수가 있겠구나 싶었다. elif문의 경우 num이 first보단 크지만 second보다 작거나 같은 경우에 second를 update를 하는 것을 의미하며, 마지막 else에서는 num이 first와 second보다 큰 경우를 지칭한다. 흠 이게 이렇게 암시적인 느낌으로 코딩할 수가 있구나...좀 신기하다.

아래는 예시.

Example Walkthrough
Let's see how this approach works on an example:

Example Input: nums = [2, 1, 5, 0, 4, 6]

first = inf, second = inf

We start iterating:
num = 2: 2 is smaller than first, so we set first = 2.
num = 1: 1 is smaller than first, so we set first = 1.
num = 5: 5 is greater than first but smaller than second, so we set second = 5.
num = 0: 0 is smaller than first, so we set first = 0.
num = 4: 4 is greater than first but smaller than second, so we set second = 4.
num = 6: 6 is greater than both first and second, so we return True (we found the triplet 0, 4, 6).