原贴地址：https://dawnmagnet.github.io/algorithm-station/docs/2022/1/12

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

示例 1：

**输入：**nums = [1,2,3,4,5]
**输出：**true
**解释：**任何 i < j < k 的三元组都满足题意

示例 2：

**输入：**nums = [5,4,3,2,1]
**输出：**false
**解释：**不存在满足题意的三元组

示例 3：

**输入：**nums = [2,1,5,0,4,6]
**输出：**true
**解释：**三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6

提示：

• 1 &lt;= nums.length &lt;= 5 * 10<sup>5</sup>
• -2<sup>31</sup> &lt;= nums[i] &lt;= 2<sup>31</sup> - 1

**进阶：**你能实现时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案吗？

思路分析

#

在本题中，可以看出，找一个符合题目条件的三元组即可，这个三元组，要是我们好好找，再怎么也得$O(n^3)$的时间，这样肯定是不可以的，然后来分析一下题目给了我们关于三元组的哪些条件

三元组只有两个条件：下标递增和递增，下标递增这个东西好办，因为题目限制我们是$O(n)$，那么我们就只用遍历一次，而且是从前向后，那么既然只遍历一次，我们很显然要在遍历的过程中去记录三元组中前一个或者前两个数字，这样我们才能凑成三元组。

那么在遍历的时候，势必存在两个变量，我们先称其为first和second，这两个变量记录了能够和当前元素形成三元组的前两个元素（因为我们是从前向后遍历的），那么因为只能遍历一次，我们要用什么办法来尽可能凑三元组，那么大家都知道，要是出现一个很小的数，其在组成三元组的时候是很有优势的，那么一旦出现小的数字，我们就可以考虑将其与first或者second进行替换，这样就能更好地组成三元组。

这个替换是有条件的，也就是说，我们需要对当前的数字进行判断，有几个区间（因为我们记录了两个数字）。

• 当前数字小于first时，我们可以将其替换为first
• 当前数字小于second时，我们可以将其替换为second
• 当前数字大于second时，就成了呀！就形成三元组了，就返回true了呀！还算啥

所以说，只要我们按照当上述的步骤对这个数组进行一次遍历就可以获得答案，如果没有找到答案，就在最后返回false就可以了~

这样满足了题目的进阶要求中$O(n)$的时间复杂度和$O(1)$的空间复杂度（因为只使用了常数个变量）

Rust代码

#

impl Solution {
    pub fn increasing_triplet(nums: Vec<i32>) -> bool {
        let mut first = nums[0];
        let mut second = i32::MAX;
        for num in &nums[1..] {
            if num > &second {
                return true;
            } else if num > &first {
                second = *num;
            } else {
                first = *num;
            }
        }
        false
    }
}