day8 at Leetcode

5. Increasing Triplet Subsequence

3つの数字を探すのに、変数を3つ持つ必要はなく、「一番小さい候補」と「2番目に小さい候補」の2つだけで解けるらしい。

• first：今までで見た中で一番小さい値
• second：first より大きいけど、その中では一番小さい値（＝2番目の候補）
• first にも second にも当てはまらない（＝どちらより大きい）数が出てきたら、3つ揃ったことになる

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

最初 return ture / return false とタイプミスした。Pythonの真偽値は先頭大文字で True / False（小文字だと未定義変数扱いでエラーになる）。

float('inf') を初期値に使うことで、「まだ候補が見つかっていない」状態を「どんな数より大きい」という形で自然に表現できるのがポイント。[2,1,5,0,4,6] で試すと True、[5,4,3,2,1] なら False になる。