Increasing Triplet Subsequence

題目描述

給定整數陣列 nums，判斷是否存在索引 i < j < k 使得 nums[i] < nums[j] < nums[k]。

輸入：nums = [1,2,3,4,5]
輸出：true

輸入：nums = [5,4,3,2,1]
輸出：false

輸入：nums = [2,1,5,0,4,6]
輸出：true（三元組 [0,4,6]）

解題思路

初始化

first = ∞, second = ∞，分別追蹤目前看到的最小值和第二小值

遍歷陣列

用 for-each 逐一處理每個數字 num

更新 first

若 num ≤ first，把 first 更新為 num（找到更小的起點）

更新 second

若 first < num ≤ second，把 second 更新為 num（找到更好的第二個數）

找到答案

若 num > second，代表 first < second < num 三元組存在，回傳 true

程式碼

C#

csharp

public class Solution {
    public bool IncreasingTriplet(int[] nums) {
        int first = int.MaxValue, second = int.MaxValue;
        foreach (int num in nums) {
            if (num <= first)
                first = num;       // 更新最小值
            else if (num <= second)
                second = num;      // 更新第二小
            else
                return true;       // 找到第三個
        }
        return false;
    }
}

TypeScript

typescript

function increasingTriplet(nums: number[]): boolean {
    let first = Infinity, second = Infinity;
    for (const num of nums) {
        if (num <= first) first = num;
        else if (num <= second) second = num;
        else return true;
    }
    return false;
}

Python

python

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

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(1) |

只需一次遍歷 O(n)，每步做常數次比較。只用 first 和 second 兩個變數，空間 O(1)。

邊界情況

陣列長度小於 3：不可能存在三元組，直接回傳 false
嚴格遞減陣列：例如 [5,4,3,2,1]，first 不斷更新但 second 永遠不會被設值，回傳 false
含有重複元素：例如 [1,1,1,1]，需要嚴格遞增，等於的情況不算，回傳 false

圖解

nums: [2,1,5,0,4,6]

num=2→

first=2, second=∞

num=1→

first=1, second=∞

num=5→

first=1, second=5

num=0→

first=0, second=5

num=4→

first=0, second=4

num=6→

6 > 4 → true!

圖表逐步追蹤 first 和 second 的變化。關鍵轉折在 num=0 時：first 更新為 0 但 second 仍為 5（代表曾經存在比 5 小的數在前面）。num=4 時 second 更新為 4。最後 num=6 大於 second=4，找到三元組。

進階觀點

💡面試追問

first 更新後 second 還有效嗎？ 有效。second 被設值時，代表在它之前曾經存在一個比它小的數（當時的 first）。即使 first 後來被更新為更小的值，那個「historical first < second」的事實不會改變。所以 num > second 時，三元組依然成立。
如果要找長度 k 的遞增子序列？ 維護一個長度 k-1 的陣列，用類似邏輯逐一更新。更通用的做法是 LIS（Longest Increasing Subsequence）的 patience sorting 方法，時間 O(n log n)。
跟 LIS 的關係？ 本題等同於判斷 LIS 長度是否 ≥ 3。本題的 first/second 就是 patience sorting 中 tails 陣列的前兩個元素。

理解測驗

🤔 為什麼 first 更新後 second 仍然有效？

🤔 nums = [1,1,1,1] 的結果是什麼？