Leetcode 334 - Increasing Triplet Subsequence

DocumentsAlgorithms
Algorithms, Leetcode, Python
Catalogue
  1. 1. Question
  2. 2. Analysis
  3. 3. Code

Question

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

Formally the function should:

Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.
Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Example 1:

Input: [1,2,3,4,5]
Output: true
Example 2:

Input: [5,4,3,2,1]
Output: false

Analysis

因为题目要求我们找到长度为3的递增子序列，因此我们可以设置两个指针 p1 和 p2，一个指向值较小的元素，一个指向值较大的元素在遍历序列的过程中，一旦遇到值比第二个值大，那么必然存在符合条件的子序列。在遍历的同时，如果遇到值小于 p1，则将新的值赋给 p1，如果新的值大于 p1， 小于 p2，则将新的值赋给 p2。这样做将递增序列的下限下调，便于更快地找到子序列第三个元素。

由于整个过程始终保证存在 p1 的值小于 p2，因此即便 p1 指向的值次序大于 p2, 一旦当前值大于 p2，一定能找到 p1 过去或现在的某个值组成递增序列。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        p1 = p2 = float('inf')
        for x in nums:
            if x <= p1:
                p1 = x
            elif x <= p2:
                p2 = x
            else:
                return True
        return False
Comments