Increasing Triplet Subsequence

Posted on | Edited on | In | | Views:

334. Increasing Triplet Subsequence

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

题目的意思是, 给一个未排序的数组, 看是否存在 $arr[i] < arr[j] < arr[k]$. 在这里需要注意的是, $i < j < k$ 但是$i, j, k$ 不需要是连续的.

例子:
[1, 2, 3, 4, 5] -> true
[5, 4, 3, 2, 1] -> false
[5, 1, 5, 2, 0, 3] ->true

思路

首先, 这道题可以用递归的方法求. 即固定第一个数, 然后看剩下的有没有大于这个数的存在的. 这是暴力解法. 时间复杂度是$O(n^3)$. 这样的时间复杂度显然是不可以接受的. 根据题目的提示, 希望答案可以做到线性, 就是$O(n)$的时间复杂度. 那么我们就要从这个方向去努力. 意味着, 扫描一次就要求给出结果. 在这样的要求下, 如果我们在迭代过程中记住了扫过的数字的最小和次小, 那么当当前的数字比最小和次小都大的时候, 我们就可以返回true了.

首先, 我们要初始化两个变量, min和mid. 然后开始遍历数组. 当当前数字比最小要小, 那么把值赋给mid. 如果比min大, 比mid小, 那么赋值给mid. 这样, 我们可以确保 min总是被mid小. 那么, 当当前数字比min和mid都大的时候, 就返回true

Code

1
2
3
4
5
6
7
8
9
10
11
def increasingTriplet(nums):
    _min = float('inf')
    mid = min
    for n in nums:
        if n <= _min:
            _min = n
        elif n <= mid:
            mid = n
        else:
            return True
    return False

复杂度

$O(n)$, $n$为输入数组的长度

EOF