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.

https://leetcode.com/problems/increasing-triplet-subsequence/

접근

#알고리즘 #그리디

처음에는 dp를 사용해 이전까지의 최대 값을 저장하는 식으로 접근하였으나, 시간초과가 발생하였다. (O(n^2))

그래서 변수 두 개를 사용한 O(n)풀이법을 참고하였다. 3개의 증가 수열만 찾으면 되므로 first,second,third를 이용한다.
first와 second는 이미 정해져 있다 가정하고, nums을 순회하며 second보다 큰 third를 찾는다. 이 때, third의 값이 first보다 작으면 first를 갱신하고, first와 second 사이라면 second를 갱신한다.

모든 nums를 순회하였는데도 함수가 종료되지 않았으면, 조건에 맞는 부분수열이 없다고 판단하고 False를 리턴한다.

코드

class Solution:
    def increasingTriplet(self, nums: list[int]) -> bool:
        
        first, second = inf, inf
        
        for third in nums:
            
            if second < third: return True
            
            
            if third <= first: first= third    #first세팅
            else:  second = third  #second세팅
                
        return  False

효율성

시간복잡도: O(n)

Runtime: 776 ms, faster than 74.12% of Python3 online submissions for Increasing Triplet Subsequence.
Memory Usage: 24.7 MB, less than 18.64% of Python3 online submissions for Increasing Triplet Subsequence.