leetcode做题记录 —— increasing-triplet-subsequence

increasing-triplet-subsequence

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. Your algorithm should run in O(n) time complexity and 
O(1) space complexity.

Examples: 
Given [1, 2, 3, 4, 5], 
return true.

Given [5, 4, 3, 2, 1], 
return false.

increasing-triplet-subsequence 
题目大意是， 给予一个无序的数组 ，如果该数组存在长度为 3 的增长子序列就返回 true，否则返回false。 
要求的时间复杂度和的空间复杂度。

解法

建立两个变量存储前两个数，比如first, second 初始值为无穷大，遍历整个数组，判断当前遍历到的元素是否比当前的first 或 second 小，如果是就把当前的 first 或 second 换成当前元素，如果比second大，这个元素即为第三个数，直接返回true。

1.//Javascript
2.var increasingTriplet = function(nums) {
3.    let first = Infinity;
4.    let second = Infinity;
5.    for( let i = 0; i < nums.length; i++ )
6.    {
7.        let num = nums[i];
8.        if( num <= first )
9.        {
10.            first = num;
11.        }
12.        else if( num <= second )
13.        {
14.            second = num;
15.        }
16.        else
17.        {
18.            return true;
19.        }
20.    }
21.    return false;
22.};

End