题目描述

给定一个无序数组，请判断数组中是否存在长度为3的递增子序列。即：

是否存在 $i, j, k$，
满足 $arr[i] < arr[j] < arr[k]$, 其中 $0 \le i \lt j \lt k \le n - 1$。

你的算法只能用 $O(n)$ 的时间以及额外 $O(1)$ 的空间。

样例1

输入：[1, 2, 3, 4, 5],
输出：true.

样例2

输入：[5, 4, 3, 2, 1],
输出：false.

算法

(线性扫描) $O(n)$

类似于求最长上升子序列问题的优化思路。

从前往后遍历整个数组，遍历时维护2个值，分别表示：

1. 上升子序列长度为1时，该数的最小值；
2. 上升子序列长度为2时，第二个数的最小值；

为了方便叙述，我们把记录的第一个数记为 $q_1$，记录的第二个数记为 $q_2$，则 $q_1 \lt q_2$。否则，如果 $q_1 \ge q_2$，则由于 $q_2$ 是某个长度为2的上升子序列的第二个数，所以该序列的第一个数小于 $q_2$，从而小于 $q_1$，与 $q_1$ 是最小数矛盾。
然后分情况讨论，对于当前数 $x$：

• 如果 $x \lt q_1$，则把 $q_1$ 更新成 $x$。同时由于 $q_1$ 是当前最小数，所以长度为2的序列的第一个数大于等于 $q_1$，从而大于 $x$，所以不能更新 $q_2$；
• 否则，如果 $x \ge q_1$ 且 $x \lt q_2$，则 $x$ 可以接在 $q_1$ 后面，组成一个长度为2的上升序列，所以可以将 $q_2$ 更新成 $x$；
• 否则，如果 $x > q_2$，则说明找到了长度为3的上升子序列。

时间复杂度分析：整个数组只被遍历一次，所以时间复杂度是 $O(n)$，遍历时只额外记录2个变量，所以额外的空间复杂度是 $O(1)$。

C++ 代码

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        vector<int>q(2);
        int tt = -1;
        for (int x : nums)
        {
            if (tt < 0) q[ ++ tt] = x;
            else
            {
                int k = 0;
                while (k <= tt && q[k] < x) k ++ ;
                if (k <= tt) q[k] = x;
                else
                {
                    if (tt < 1) q[ ++ tt] = x;
                    else return true;
                }
            }
        }
        return false;
    }
};