334. 递增的三元子序列

一. 题目描述

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

示例 1

1
2
3
输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i < j < k 的三元组都满足题意

示例 2

1
2
3
输入：nums = [5,4,3,2,1]
输出：false
解释：不存在满足题意的三元组

示例 3

1
2
3
4
输入：nums = [2,1,5,0,4,6]
输出：true
解释：三元组 (3, 4, 5) 满足题意
因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6

提示

  • 1 <= nums.length <= 5 * 105
  • -231 <= nums[i] <= 231 - 1

二. 笔者见解

此题是一道经点的找递增下标的递增数字题，题目看似简单，时则对很多情况都有要求，在力扣中被定义为中等题。

思路 1

超级暴力解法——三个for循环，第一层是对每个数字自身，第二层对于比第一层大的数，第三层对于比第二层大的数

思路 2

找左边最小的（最优先找），找比左边第二小（第二优先），找第左第大的数

三.解题方法

1. 暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean increasingTriplet(int[] nums) {
        if(nums.length<3){return false;}
        int n = nums.length,min;
        for (int i = 0; i < n; i++) {
            min = nums[i];
            for (int j = i+1; j < n; j++) {
                if(min<nums[j]){
                    for (int k = j; k < n; k++) {
                        if(nums[k]>nums[j]){return true;}
                    }
                }
            }
        }
        return false;
    }
}

image.png

2. 超简单解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean increasingTriplet(int[] nums) {
     if(nums.length<3){return false;}
        int min = Integer.MAX_VALUE;
        int mid =Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]<=min){
                min = nums[i];
            }else if(nums[i]<=mid){
                mid = nums[i];
                //System.out.println(min+" "+mid);
            }else {
                return true;
            }
        }
        return false;
    }
}

image.png

四.总结感悟

让我们用数组[1,9,5,0,6]来模拟,输出左边第一、第二小的数

第一次——1 9

第二次——1 5

第三次——0 5

第四次——6比5大输出

这是会有小伙伴有疑问，第三次的 0 的位置在5的右边，不符合题意，实际上我们不能这么思考。

0虽然在5的右边，但5的左边一定存在一个比5小的数，在本题中是1，这样我们在5的后面找到一个比5大的数，就找到了，递增的三元子序列