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

给一个非排序的数组，判断是否存在一个长度为3的递增子序列。要求：T: O(n) S: O(1)

解法：由于时间和空间复杂度的要求，不能用排序或者DP的方法。遍历数组，用两个变量分别记录当前的最小值和第二小的值，如果发现一个比这两个都大的数，则组成了一个长度为3的子序列，返回True。如果遍历结束，没找到返回False。

Java:

public boolean increasingTriplet(int[] nums) {

        // start with two largest values, as soon as we find a number bigger than both, while both have been updated, return true.

        int small = Integer.MAX_VALUE, big = Integer.MAX_VALUE;

        for (int n : nums) {

            if (n <= small) { small = n; } // update small if n is smaller than both

            else if (n <= big) { big = n; } // update big only if greater than small but smaller than big

            else return true; // return if you find a number bigger than both

        }

        return false;

    }

Python:

def increasingTriplet(nums):

    first = second = float('inf')

    for n in nums:

        if n <= first:

            first = n

        elif n <= second:

            second = n

        else:

            return True

    return False

C++:

bool increasingTriplet(vector<int>& nums) {

    int c1 = INT_MAX, c2 = INT_MAX;

    for (int x : nums) {

        if (x <= c1) {

            c1 = x;           // c1 is min seen so far (it's a candidate for 1st element)

        } else if (x <= c2) { // here when x > c1, i.e. x might be either c2 or c3

            c2 = x;           // x is better than the current c2, store it

        } else {              // here when we have/had c1 < c2 already and x > c2

            return true;      // the increasing subsequence of 3 elements exists

        }

    }

    return false;

}

All LeetCode Questions List 题目汇总

巴特西

[LeetCode] 334. Increasing Triplet Subsequence 递增三元子序列

All LeetCode Questions List 题目汇总

最新文章

热门文章