【LeetCode 334】递增的三元子序列

一时失言乱红尘 2022-11-27 15:40 192阅读 0赞

#### 题目描述 ####

给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。

数学表达式如下:

> 如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1， 使得 arr\[i\] < arr\[j\] < arr\[k\]  
> ，返回 true ; 否则返回 false 。 说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1) 。

示例 1:

输入: [1,2,3,4,5]
    输出: true

示例 2:

输入: [5,4,3,2,1]
    输出: false

#### 解题思路 ####

**方法一：**

我们可以设置两个变量one和two，保证one小于two，若遍历到一个数大于two，则满足三个数递增的要求，返回true

该方法的**时间复杂度为O(n)**，**空间复杂度为O(1)**。

**方法二：**

我们还可以使用**贪心算法**来解决这个问题。

循环遍历数组，不断更新数组中出现的最大值和最小值，如果出现一个大于最大值的数，则表示存在长度为3的递增子序列，返回true。

具体步骤如下：

*  首先定义两个变量small和big，分别存放三个数字中的比较小的两个，
 *  循环数组，实时捕获最小的两个数，同时判断这个两个数后面是否存在一个数比这两个数都大，如果存在，就返回true，否则就返回false。

该方法的**时间复杂度为O(n)**，**空间复杂度为O(1)**。

#### 代码实现 ####

**方法一：**

/** * @param {number[]} nums * @return {boolean} */
    var increasingTriplet = function(nums) { 
        if(nums.length < 3) return false
    
        let one, two
        for(const num of nums){ 
            if(num > two){ 
                return true
            }else if(num > one){ 
                two = num
            }else{ 
                one = num
            }
        }
        return false
    };

**方法二：**

/** * @param {number[]} nums * @return {boolean} */
    var increasingTriplet = function(nums) { 
        if(nums.length < 3) return false
        let small = Number.MAX_SAFE_INTEGER
        let big = Number.MAX_SAFE_INTEGER
    
        for(let i = 0; i< nums.length; i++){ 
            if(nums[i] <= small){ 
                small = nums[i]
            }else if(nums[i] <= big){ 
                big = nums[i]
            }else{ 
                return true
            }
        }
        return false
    };

##### 提交结果 #####

**方法一：**  
![在这里插入图片描述][20200816002619977.png]  
**方法二：**  
![在这里插入图片描述][20200816003637819.png]

[20200816002619977.png]: /images/20221124/ffe2dbed91854ba6a9ea51cf82c5321e.png?
[20200816003637819.png]: /images/20221124/b9fb1e004cda4ec1bbf9972902eb6115.png?