递增的三元子序列

给定一个未排序的数组,判断这个数组中是否存在长度为 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

暴力破解法,时间耗费的是 O(N*N*N)。如果是需要找递增的二元组的话完全可以使用 O(N)的遍历方法,但是在解题中,第二个数和第三个数进行对比的前提是第二个数大于第一个数,而这个前提又是基于对数组的遍历,所以形成了 O(N*N*N)。
可以想到的优化是第一个循环用来一边遍历一边对比,对比为真时再进入下一个循环,这时的空间复杂度为 O(N*N)
如果不想嵌套下一个循环的,可以使用数组将比较完成的状态进行存储。另开一个循环,对比遍历时使用数组中的数据得出结果,这种方法的空间复杂度是O(N)。

空间复杂度O(1)的思路有点类似动态规划的思想,维护一个二元组(first,second),记录第i个元素之前的“最小”递增二元子序列(对后续元素的要求最低如[5,6,2,3,4]会更新[5,6]为[2,3]此时只要后续满足大于3就可以)
当nums[i]小于first时,更新first的值
当nums[i]>first且nums[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//O(n)
    public static boolean increasingTriplet(int[] arr) {
        if(arr.length <= 2)
            return false;
        int n = arr.length;
        boolean[] hasfirstsmall = new boolean[n];
        int smallest = arr[0];
        hasfirstsmall[0] = false;
        for(int i = 0;i<arr.length;i++) {
            if(smallest < arr[i]) {
                hasfirstsmall[i] = true;
                }
            smallest = Math.min(smallest, arr[i]);
        }
        int biggest = arr[n-1];
        for(int i = n-2;i>=0;i--) {
            if(hasfirstsmall[i] == true) {
                if(arr[i] < biggest)
                    return true;
                biggest = Math.max(biggest, arr[i]);
            }
        }
        return false;
    }
    //O(1)
    public static boolean increasingTriplet2(int[] arr) {
        if(arr.length <= 2)
            return false;
        int first = Integer.MAX_VALUE;
        int second = Integer.MAX_VALUE;
        for(int i = 0;i<arr.length;i++) {
            System.out.println(i);
            if(arr[i] <= first) {
                first = arr[i];
                continue;
            }
            if(arr[i] > first && arr[i] <= second) {
                second = arr[i];
                continue;
            }
            if(arr[i] > second) {
                return true;
            }  
        }
        return false;
    }
0 条评论
发表一条评论