首页 > itarticle > leetcode334. 递增的三元子序列

leetcode334. 递增的三元子序列

admin 11月 14, 2020 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/increasing-triplet-subsequence

解题思路

第一步：转化题目，求长度为3的递增子序列，等同于维护3个下标，如题目所述。
第二步：使用2个变量保存最小的2个数值，即min1为数组当前的最小值，min2为第二小的值。
第三步：如果出现小于min1的值，更新min1；如果出现小于min2的值，更新min2。（本人所写代码中使用了小于等于，是因为要排除等于的情况）
第四步：如果找到大于min2的数，则说明存在长度为3的递增子序列

代码如下

class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums.length < 3) return false;
        int min1 = nums[0];
        int min2 = Integer.MAX_VALUE;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] <= min1) {
                min1 = nums[i];
            } else if (nums[i] <= min2) {
                min2 = nums[i];
            } else {
                return true;
            }
        }
        return false;
    }
}

提交结果