解題說明
Increasing Triplet Subsequence
題目描述：給定一個整數陣列 nums，判斷是否存在三個索引 i < j < k，使得 nums[i] < nums[j] < nums[k]。若存在則回傳 true，否則回傳 false。
解題思路：核心想法是 Greedy（貪婪法）——維護兩個變數 first 和 second，分別代表目前掃描到的「最小值」與「最小的第二小值（且 second > first）」。
從左到右遍歷陣列中的每個元素 num：
- 若
num <= first：更新first為num（找到更小的第一個數）。 - 否則若
num <= second：更新second為num（在first之後找到更小的第二個數）。 - 否則（
num > second）：此時num就是第三個遞增的數，直接回傳true。
關鍵直覺在於：即使 first 在後來被更新為一個更小的值（其位置可能在 second 之後），second 的存在已保證在某個更早的索引之後確實有一個比 second 小的值存在，因此只要後續出現 num > second，三元組就成立。整個過程只需 O(n) 時間、O(1) 空間。
C++ 解法
複雜度分析
時間複雜度：O(n) — 只需一次線性掃描整個陣列，每個元素恰好處理一次。
空間複雜度：O(1) — 只使用兩個額外變數 first 與 second，不隨輸入規模增長。
虛擬碼
1. Initialize first = +∞, second = +∞
2. For each num in nums:
a. If num <= first:
- Set first = num
b. Else if num <= second:
- Set second = num
c. Else:
- Return true (num > second > first: triplet exists)
3. Return false其他解法
動態規劃 O(n²)：對每個位置 j 分別掃描其左側最小值與右側最大值，判斷是否能構成三元組。時間複雜度 O(n²)、空間 O(n)，思路直觀但效率較低，不推薦用於此題。
Patience Sorting / LIS 長度 O(n log n)：使用求最長遞增子序列（LIS）長度的 patience sorting 方法，若 LIS 長度 ≥ 3 則回傳 true。時間 O(n log n)、空間 O(n)，邏輯較為通用（可推廣至「是否存在長度 k 的遞增子序列」），但本題只需判斷長度 3，Greedy 兩變數法已是最優選擇。
延伸思考
- 若要求找出長度為 k（而非固定為 3）的遞增子序列是否存在，演算法要如何修改？時間複雜度會如何變化？
- 如果題目改為需要回傳滿足條件的三個索引
(i, j, k)而非僅判斷是否存在，現有的貪婪做法需要做哪些調整？ - 如果陣列中可能包含重複元素，且條件改為嚴格遞增（
nums[i] < nums[j] < nums[k]），現有解法是否仍然正確？請驗證邊界情況（例如[2, 2, 2]、[1, 1, 2]）。