leetcode IncreasingTripletSubsequence
z
 2019-04-09 10:36:27   
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
47
48
49
public class IncreasingTripletSubsequence {
  /**
   * 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
   */
  public boolean increasingTriplet(int[] nums) {
    int[] t = new int[3];
    t[0] = Integer.MIN_VALUE;
    int idx = -1;
    for (int i=0; i<nums.length; i++){
      if (idx == -1)
        t[++idx] = nums[i];
      else{
        if (nums[i] > t[idx]){
          t[++idx] = nums[i];
        }
        else if (nums[i] < t[idx]){
          if (idx == 1 || nums[i] < t[0]){
            t[0] = nums[i];
          }
          else if (nums[i] > t[0] && nums[i] < t[1]){
            t[i] = nums[i];
          }
        }
        else{
          continue;
        }
      }
      if (idx == 2){
        return true;
      }
    }
    return false;
  }
}