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.

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        for i in range(len(nums)-2):
            if nums[i] < nums[i+1] and nums[i+1] < nums[i+2]:
                return True

        return False

처음엔 그냥 3연속이면 되는건가 쉽네 했는데 아녔음 ㅎ

My Answer 1: Accepted (Runtime: 3968 ms - 7.99% / Memory Usage: 14.8MB - 49.89%)

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        for i in range(len(nums)-2):
            numlist = []
            for j in range(i+1, len(nums)):
                if nums[i] < nums[j]:
                    numlist.append(nums[j])
            for j in range(len(numlist)-1):
                if numlist[j] < numlist[j+1]:
                    return True

        return False

7퍼 런타임의 주인공 이중 for 문..^^

1. 각 숫자마다 자신보다 큰 값들을 numlist 에 저장
2. numlist 중에 numlist[j] < numlist[j+1] 가 있으면 True 리턴

딕셔너리를 써서도 해보려했지만.. 드러워짐

Time Complexity:O(n) and Space:O(1)

Solution 1: Runtime: 56 ms - 57.56% / Memory Usage: 14.7 MB - 93.66%

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        f_min = float('inf')
        s_min = float('inf')
        for i in range(len(nums)):
            if nums[i] <= f_min:
                f_min = nums[i]
            elif nums[i] <= s_min:
                s_min = nums[i]
            else:
                return True
        return False

f_min 과 s_min 에 무한대 값으로 초기화한 후 first, second 최솟값 찾기

1. when nums[i] <= first_min, update first_min with nums[i]
2. when first_min < nums[i] <= second_min, update second_min with nums[i]
3. when nums[i] > second_min, good! we find the third element!