leetcode334.Increasing Triplet Subsequence

发表于 更新于 分类于 ，

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

假设有一个无序的数组，如果数组中从左到右存在三个由小到大的数字，则返回true。否则返回false。

题目的额外要求是：O(n)的时间复杂度和O(1)的空间复杂度

思路一: 找到中间位置

其实我们知道只要找到这样一个数字，该数字左边存在比它小的数字，右边存在比它大的数字，就可以确信该数字一定属于某个上升序列的中间数字。所我们可以先从左往右得出每一个数字左边是否有比它小的数字，再从有望走得出右边是否有比它大的数字，最后再根据这两个信息判断该数字是否为上升序列的中间数字。

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
public boolean increasingTriplet(int[] nums) {
    if(nums == null || nums.length < 3) return false;
    
    boolean[] hasLeftMin = new boolean[nums.length];
    boolean[] hasRightMax = new boolean[nums.length];
    
    int left = 0;
    int right = nums.length - 1;
    for(int i = 1 ; i<nums.length-1 ; i++) {
        if(nums[i] > nums[left]) {
            hasLeftMin[i] = true;
        } else {
            left = i;
        }
        if(nums[nums.length - i - 1] < nums[right]) {
            hasRightMax[nums.length - i - 1] = true;
        } else {
            right = nums.length - i - 1;
        }
    }
    
    for(int i = 1 ; i < nums.length - 1 ; i++) {
        if(hasLeftMin[i] && hasRightMax[i]) return true;
    }
    return false;
}

这种思路虽然遵循了O(N)的时间复杂度，但是违背了O(1）的空间复杂度

思路二：找到最小的两个数字

思路二是从讨论区排名第一的回答中挖过来的。这个思路实在是非常的独特，而且精炼！这里它用两个变量分别记录了已经遍历过的数字中最小的数字和第二小的数字，一旦找到比这两个数字都大的数字就证明一定存在一个升序。

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean increasingTriplet(int[] nums) {
    int small = Integer.MAX_VALUE, big = Integer.MAX_VALUE;
    for(int n : nums) {
        if(n <= small) {
            small = n;
        } else if (n<=big) {
            big = n;
        } else {
            return true;
        }
    }
    return false;
}