LeetCode 334: Increasing Triplet Subsequence

對於這題的初步想法是，應該只需要跑一次就夠了， 再來需要一個變數儲存最小值、另一個變數儲存次小值，如果有找到任何一個數大於他們，就通過了。

題目

題目連結：LeetCode 334. Increasing Triplet Subsequence

給定一個整數陣列 nums，判斷是否存在三個 index $i < j < k$，使得 $nums[i] < nums[j] < nums[k]$。如果存在，回傳 true；否則回傳 false。

Example:

• Input: nums = [2, 1, 5, 0, 4, 6]
• Output: true（0 < 4 < 6）

時間複雜度要在 $O(n)$，空間複雜度 $O(1)$。

貪婪演算法

想像我們在填三個坑：first、second、和最後要找的 third。

• first：目前看到的最小值。遇到更小的就換掉。
• second：比 first 大。遇到比 first 大又比 second 小的就換掉。
• third：只要出現任何比 second 大的數，就找到了，直接回傳 true。

初始值設成無限大 float('inf') 代表「坑還沒被填」。

走一遍範例

用 nums = [2, 1, 5, 0, 4, 6] 跑一遍：

Table: 實際走訪過程

要用 >= 而不是 >

第一次提交的時候，沒有想到邊界情況，當如果有重複的數字，或是所有數字都一樣呢？

如果 nums 裡有重複數字，用單純的 > 會把相同數字當作「更大的數」處理，導致誤判。 應改為 >= 確保 first 和 second 的更新條件包含等號。

覆蓋 first 會不會破壞 second？

看到 first 被 0 覆蓋，second 還是 5，可能會覺得奇怪：first < second 的關係還成立嗎？

其實 second 記錄的是「當時記錄它的那個 first」確實比它小，這個事實不會因為 first 之後被更新而消失。

所以只要某個數比 second 大，就一定存在一個更早的 first 比 second 小，這樣三個遞增就成立了。

程式碼

from typing import List

def increasingTriplet(nums: List[int]) -> bool:
    first = float('inf')
    second = float('inf')

    for i in nums:
        if first >= i:
            first = i
        elif second >= i:
            second = i
        else:
            # 有數字比 first、second 都大
            return True

    return False

複雜度

• 時間複雜度：$O(n)$。一次遍歷完成。
• 空間複雜度：$O(1)$。只用了 first、second 兩個變數。

小結

這題的精髓是「不需要記住三元組的實際數字是什麼，只需要知道它存不存在」。Greedy 的思維在我們要盡量讓 first 和 second 越小越好，這樣越容易被後面的數字超越。

類似「維護最小值哨兵」的技巧在 121. Best Time to Buy and Sell Stock 也有用到，可以一起練習看看唷。