跳转至

LeetCode: 334. 递增的三元子序列

1、题目描述

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

数学表达式如下:

如果存在这样的 i, j, k, 且满足 0 ≤ i < j < kn-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

2、解题思路

  • 设计两个数,m1,m2,初始化为整数最大值
  • 如果当前数小于等于m1,更新m1
  • 如果大于m1,小于等于m2,更新m2
  • 如果大于m2,返回真
class Solution:
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums) < 3:
            return False

        m1 = 2 ** 32 - 1
        m2 = 2 ** 32 - 1

        for i in nums:
            if m1 >= i:
                m1 = i
            elif m2 >= i:
                m2 = i
            else:
                return True

        return False