334. Increasing Triplet Subsequence

[fockspaces]

這題真的難... 最後靠 GPT 給 hint 才解出開

1. 找 triplet，定義 (head, tail, num) 作為查詢指標
2. head = tail = inf，表示預設絕對不會形成有序 triplet
3. iterate list, 這邊比較 tricky a. 當 num 同時比 head, tail 都小，把它交給 tail b. 當 num 只比 head 小，把它交給 head（greedy 的概念） c. 當 num 比 head, tail 都大，代表此時 (tail, head, num) 形成有序數組

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        left = right = float('inf')
        for num in nums:
            if num < right and num < left:
                left = num
            elif num < right and num > left:
                right = num
            elif num > right and num > left:
                return True

        return False