题目描述

blablabla

样例

blablabla

算法1

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

y总讲的太复杂了。不需要参考最长上升子序列的做法，回归这道题的本质，其实是 维护一个最小值和一个次小值即可。

我们分三种情况说明：

a. 当前枚举的数x 比 次小值大的时候，说明找到了自增三元组。

b. 当枚举的x，大于最小值，小于次小值的时候，次小值变为当前值x。

c. 当枚举的x，小于最小值的时候，最小值变成当前值x。次小值不需要改变。

通过以下两种情况说明为啥次小值不需要改变：

1. 遇到的下一个x 如果比次小值大，则 改变前的最小值 与 当前次小值 和 x 组成递增三元组，且符合前后顺序。
2. 遇到的下一个x 如果小于当前次小值且大于当前最小值，则对应了上面的情况b，次小值变成了x，与当前最小值组成了一个更优的组合。

python 代码

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        n = len(nums)
        if n <= 2:
            return False
        mx1 = nums[0]
        mx2 = inf
        for i in range(1, n):
            if nums[i] > mx2:
                return True
            if mx1 < nums[i] < mx2:
                mx2 = nums[i]
            if nums[i] < mx1:
                mx1 = nums[i]
        return False