leetcode [334] 递增的三元子序列

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

给定一个未排序的数组，判断这个数组中是否存在长度为 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

来自题解:

递增子序列通用解法，维护一个窗口，按照递增序列保存，如果当前值大于窗口最大值，加入，否则往前遍历，直到找到小于当前值的位置，替换该值。

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        if len(nums) < 3:
            return False

        win = [nums[0]]

        for num in nums:
            if num > win[-1]:
                win.append(num)
                if len(win) >= 3:
                    return True
            else:
                i = len(win) - 1
                while i > 0 and win[i-1] >= num:
                    i -= 1
                
                win[i] = num
        return False