Increasing Triplet Subsequence

334. 递增的三元子序列

分析

核心思想：
- 使用一个长度为 2 的数组 q 来记录递增子序列中的前两个元素：
  - q[0] 表示递增子序列中的最小元素
  - q[1] 表示递增子序列中第二小的元素
- 遍历数组，根据当前数字和 q 中的元素关系更新状态
遍历逻辑：
- 如果当前数字 num 小于等于 q[0]，更新 q[0] 为更小的数字
- 如果当前数字大于 q[0] 且小于等于 q[1]，更新 q[1] 为更小的数字
- 如果当前数字大于 q[1]，说明找到了满足条件的递增三元组 q[0], q[1], num，返回 true
返回结果：
- 若遍历结束后仍未找到满足条件的三元组，则返回 false

时间复杂度

遍历数组一次，每次更新双指针数组最多需要 O(1) 的时间

总时间复杂度为 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution
             {
public:
    bool increasingTriplet(vector<int>& nums)
    {
        // 初始化递增子序列的前两个元素为无穷大
        std::vector<int> q(2, INT_MAX);

        for (int num : nums)
        {
            int k = 2; // 初始化目标位置为第 3 位
            while (k > 0 && q[k - 1] >= num) // 寻找插入位置
                --k;

            if (k == 2) // 如果找到了递增三元组
                return true;

            q[k] = num; // 更新 q 中对应位置的值
        }

        return false; // 遍历结束仍未找到三元组
    }
};