[LeetCode] 334. 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.

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

递增的三元子序列。

题意是给一个未排序的数组，请问数组中是否存在三个元素是单调递增的。

设两个变量firstSmall和secondSmall，初始化都设置成Infinity。这样在遍历数组的时候可以找到第一小和第二小的数字。当遇到第三个数字小于Infinity但是大于前两者时，就找到了triplet。

注意所谓的subsequence可以是不连续的，如下testcase一样可以通过。[1,3,2,4,0]

时间O(n), n == nums.length

空间O(1)

Java实现

 1 class Solution {
 2     public boolean increasingTriplet(int[] nums) {
 3         int first = Integer.MAX_VALUE;
 4         int second = Integer.MAX_VALUE;
 5         for (int num : nums) {
 6             if (num <= first) {
 7                 first = num;
 8             } else if (num <= second) {
 9                 second = num;
10             } else {
11                 return true;
12             }
13         }
14         return false;
15     }
16 }

JavaScript实现

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