334. Increasing Triplet Subsequence (1)

Link

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

Solution

當minValue1再次更新時(找到比當下更小的value)，minValue2似乎沒有update到。但這樣不影響邏輯，因為更新前minValue一定比minValue2小，所以能夠找到第三個數字小於minValue2那必定小於之前的minValue1，滿足找到三個增加的數字。

 public boolean increasingTriplet(int[] nums) {
        int minValue1 = Integer.MAX_VALUE;
        int minValue2 = Integer.MAX_VALUE;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] <= minValue1){
                //當minValue1再次更新時(找到比當下更小的value)，
                //minValue2似乎沒有update到。但這樣不影響邏輯，
                //因為更新前minValue一定比minValue2小，所以能夠找到第三個數字
                //小於minValue2那必定小於之前的minValue1，滿足找到三個增加的數字。
                minValue1 = nums[i];
            }
            else if (nums[i] <= minValue2){
                minValue2 = nums[i];
            }
            else{
               return true;
            }
        }
        return false;
    }
}