[Leetcode]334: Increasing Triplet Subsequence

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

Problem:
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.

圖來自leetcode

Thoughts：
1. 直接跑array內的值(nums[i] < nums[j] < nums[k])做比較，i<j<k這個照迴圈跑就可以達成。
2. first, second先設為 infinity，然後比較小的值取代掉 first, second
3. 假設 nums =[2,1,5,0,4,6]
num, first, second = [2, 2, inf]
num, first, second = [1, 1, inf]
num, first, second = [5, 1, 5]
num, first, second = [0, 0, 5]
num, first, second = [4, 0, 4]
num = 6, [0, 4, 6]

Solution:

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

time complexity = O(n)