解題說明
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])。