334. Increasing Triplet Subsequence

📘 題目敘述

給定一個整數陣列 nums，請判斷是否存在三個索引 i < j < k，使得：

nums[i] < nums[j] < nums[k]

若存在，回傳 true；否則回傳 false。

條件限制

• 1 ≤ nums.length ≤ 5 * 10^5
• -2^31 ≤ nums[i] ≤ 2^31 - 1

🧠 解題思路（一）（直覺）

我這份程式的想法是：我想要一路掃過陣列，維持一組「可能形成遞增三元組」的前兩個值：

• first：目前選到的第一個數（希望越小越好）
• second：目前選到的第二個數（要大於 first，且也希望越小越好）

只要後面出現一個數 > second，就代表我找到了：first < second < nums[i] → 直接回傳 true。

但我在寫的時候多加了一個變數 nfst，用來記錄「目前看到的更小的第一個候選值」，讓我可以在某些情況下把 first 更新得更合理（例如遇到更小的值時先存起來，等到找到適合的 second 才一起更新）。

所有變數

• first：目前候選的第一個值（前面那個小的）
• second：目前候選的第二個值（要比 first 大），一開始設成 2147483647 當作無限大
• nfst：我額外記的「新的 first 候選值」（遇到更小的數先放這裡）
• i：掃描陣列用的索引

🪜 主要流程步驟

1. 先處理不可能的情況

• 如果 nums.size() < 3，不可能有三個數，直接回傳 false

2. 初始化候選值

• first = nums[0]
• second = INT_MAX（代表目前還沒有找到合適的第二個數）
• nfst = nums[0]（先用第一個數當作初始「新 first 候選」）

3. 逐個掃描 nums[i]，更新候選或判斷成功

我從 i = 1 開始掃，對每個 nums[i] 分三種情況：

情況一：nums[i] > second 直接成功

• 這表示我已經有一組 (first, second)
• 現在又出現一個更大的 nums[i]
• 所以形成 first < second < nums[i] → 立刻回傳 true

情況二：nums[i] 可以當作「更好的 second」

判斷式是：

• nums[i] < second 表示它比目前的 second 更小（更好）
• (nums[i] > first || nums[i] > nfst) 表示它要能當第二個數（必須比第一個候選大）

如果符合這個條件：

• 我會把 first 更新成 nfst
• 把 second 更新成 nums[i]

直覺意思是：我找到一個更好的「第二個數」，那我就把第一個數也一起換成我目前記著更小的 nfst，讓 (first, second) 更可能接到後面的第三個數。

情況三：以上都不符合 → 更新 nfst

• 我就把 nfst = nums[i]

這代表：目前這個值不適合當 second（可能太小或破壞遞增），但它可能成為未來更好的第一個候選，所以先記起來。

4. 全部掃完還沒成功

• 代表過程中一直找不到 > second 的第三個數
• 回傳 false

💻 程式碼實作

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        if (nums.size() < 3) {
            return false;
        }
        int first = nums[0], second = 2147483647;
        int nfst = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > second) {
                return true;
            } else if (nums[i] < second && (nums[i] > first || nums[i] > nfst)) {
                first = nfst;
                second = nums[i];
            } else {
                nfst = nums[i];
            }
        }
        return false;
    }
};

🧠 解題思路（二）Greedy

這題我的核心想法是：

不需要真的找出三個數字，只要能確定「存在可能性」即可。

我在掃描整個陣列的過程中，只維護兩個狀態：

• fst：目前為止，能當作「第一個數」的最小值
• snd：在 fst 之後，能當作「第二個數」的最小值

如果在之後的掃描中，出現一個數字 x，使得：

fst < snd < x

那代表遞增三元子序列一定存在，可以直接回傳 true。

所有變數

• fst：目前找到的最小值，作為遞增序列的第一個數
• snd：在 fst 之後，找到的次小值，作為第二個數
• nums[i]：目前正在掃描的陣列元素

🪜 主要流程步驟

1. 初始化兩個狀態變數

• 將 fst 與 snd 都初始化為非常大的值（例如 INT_MAX）
• 表示目前還沒選到任何有效的第一、第二個數

2. 由左到右掃描整個陣列

對每一個 nums[i]，依序判斷：

情況一：nums[i] <= fst

• 代表找到了一個「更小的第一個數」
• 更新：

fst = nums[i]

情況二：nums[i] > fst 且 nums[i] <= snd

• 代表這個數字可以當作「第二個數」
• 更新：

snd = nums[i]

情況三：nums[i] > snd

• 代表已經找到：fst < snd < nums[i]
• 遞增三元子序列成立
• 直接回傳 true

3. 掃描結束仍未成功

• 若整個陣列掃完都沒有進入情況三
• 代表不存在遞增三元子序列
• 回傳 false

為什麼像 2 3 -1 4 這種情況也會回傳 true？

這是這題 最容易誤解、但其實非常關鍵的一點。

我們用這組輸入實際走一次流程：

nums = [2, 3, -1, 4]

狀態變化過程

1. 讀到 2

   • fst = 2
   • snd = +∞

2. 讀到 3

   • snd = 3
   • 此時已經有潛在組合：2 < 3

3. 讀到 -1

   • -1 <= fst
   • 更新：

   fst = -1
   

   • 此時狀態變成：fst = -1, snd = 3
   • 我只是把「第一個數」換成更小的值
   • 並沒有破壞「第二個數」的有效性
   • snd = 3 仍然是合法的第二個數候選

4. 讀到 4

   • 4 > snd
   • 成立：-1 < 3 < 4
   • 回傳 true

為什麼這樣是正確的？

因為題目找的是 子序列（subsequence）：

• 不要求連續
• 只要求索引遞增

所以：

• fst 和 snd 不一定要來自同一段連續區間
• 只要存在某個順序能滿足大小關係即可

這也是 Greedy 解法能成立的根本原因。

💻 程式碼實作 (Greedy)

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int fst = 2147483647, snd = 2147483647;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] <= fst) {
                fst = nums[i];
            } else if (nums[i] <= snd) {
                snd = nums[i];
            } else {
                return true;
            }
        }
        return false;
    }
};

🔗 題目連結

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