186 - 334 递增的三元子序列

题目

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

数学表达式如下:

如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1， 使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。 说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1) 。

示例 1:

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

示例 2:

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

解答

一开始感觉这是一道，滑动窗口的问题。

但是题目并没有要求连续，只需要三个数是递增的，可以跳开递增。

存两个变量的方法：

https://leetcode-cn.com/problems/increasing-triplet-subsequence/solution/shi-yong-shuang-zhi-zhen-qiu-jie-by-liu-fei-3/

因此，可以用两个变量，存最小值和中间值，如果遇到比中间值更大的，就直接有答案了。

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        small = float('inf')
        mid = float('inf')
        for num in nums:
            if num < small:
                small = num
            elif num > small and num < mid:
                mid = num
            elif num > mid:
                return True
        return False

Runtime: 52 ms, faster than 91.54% of Python3 online submissions for Increasing Triplet Subsequence.

Memory Usage: 13.3 MB, less than 100.00% of Python3 online submissions for Increasing Triplet Subsequence.