LeetCode 遞增三元子序列：貪心雙變量 O(n) 時間 O(1) 空間

題目描述

給定無序數組，判斷是否存在下標 i < j < k 使 nums[i] < nums[j] < nums[k]。要求 O(n) 時間、O(1) 空間。

核心觀察

只需維護最小的兩個遞增元素 a、b（a < b）。遍歷過程中：

• 若 x ≤ a → 更新 a = x（找到更小的起點）
• 若 a < x ≤ b → 更新 b = x（找到更小的中間值）
• 若 x > b → 直接返回 true（構成三元組）

此貪心策略保證 a、b 始終是「最有潛力」構成三元組的最小前綴。

C++ 實現

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int a = INT_MAX, b = INT_MAX;
        for (int x : nums) {
            if (x <= a) a = x;
            else if (x <= b) b = x;
            else return true; // x > b，構成 a < b < x
        }
        return false;
    }
};

正確性直覺

儘管 a、b 可能不來自最終三元組（如 [5, 1, 5, 2, 3] 中 a=1, b=2 實際對應 1,2,3），但只要存在合法三元組，算法必能找到某組有效的 a,b。因為 a 單調非增、b 在 a 確定後單調非增，永不錯過機會。

複雜度

• 時間 O(n)：單次遍歷。
• 空間 O(1)：兩個整數變量。

延伸

通用化：尋找長度 k 遞增子序列可維護大小 k-1 的數組，時間 O(n log k)（二分查找更新），即 LIS 的在線版本。