題目：給定未排序數組，判斷是否存在長度為 3 的遞增子序列 (索引 `i < j < k` 且 `nums[i] < nums[j] < nums[k]`)。要求 **O(n) 時間、O(1) 空間**。
示例：`[1,2,3,4,5]` → `true`；`[5,4,3,2,1]` → `false`。
// 典型暴力：三層循環檢查所有三元組
for (int i = n-1; i >= 2; i--)
for (int j = i-1; j >= 1; j--)
if (nums[i] > nums[j])
for (int k = j-1; k >= 0; k--)
if (nums[j] > nums[k]) return true;
return false;缺陷：時間 O(n³)，空間 O(1)。大數據超時，未利用題目「只需存在性」特性。
核心思想：遍歷數組，維護兩個變量：
first：迄今遇到的最小值 (潛在三元組第一個數)。second：迄今遇到的、大於 first 的最小值 (潛在三元組第二個數)。一旦遇到數字 `num > second`，即構成 `first < second < num`，直接返回 `true`。遍歷結束未觸發則返回 `false`。
public boolean increasingTriplet(int[] nums) {
int first = Integer.MAX_VALUE;
int second = Integer.MAX_VALUE;
for (int num : nums) {
if (num <= first) {
first = num; // 更新最小值
} else if (num <= second) {
second = num; // 更新中間值 (比 first 大但盡可能小)
} else { // num > second
return true; // 找到 third，三元組成立
}
}
return false;
}first 永遠記錄「截止當前、能作為三元組起始的最小值」。越小越容易滿足後續遞增。second 記錄「截止當前、能作為三元組中間值的最小值」（前提是已有 `first`）。它只在 `num > first` 時才可能更新，且取最小的符合條件者，留最大空間給第三個數。同理維護大小為 `k-1` 的數組 `candidates[]`，遍歷更新。時間 O(n log k) (二分查找插入位置) 或 O(nk) (線性掃描)。空間 O(k)。本題 k=3 退化為 O(1) 空間。
| 方法 | 時間 | 空間 | 備註 |
|---|---|---|---|
| 三層循環暴力 | O(n³) | O(1) | 超時 |
| DP 最長遞增子序列 (LIS) | O(n²) | O(n) | 過度殺傷 |
| 貪心雙變量 (標準解) | O(n) | O(1) | 完美滿足要求 |
