334. Increasing Triplet Subsequence

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

贪心算法。
将first与second初始化为最大值。
first保存遍历过的最小值。
second保存遍历过的大于之前最小值的最小值。

遍历数组。
条件一：如果数字小于现在第一个值，则更新第一个值。
（此时一定不满足条件二，因此可以安全地更新更小的数字。）
条件二：如果数字大于第一个值，且小于第二个值，则更新第二个值。
（此时第一个值已经被更新过了，满足第一个值小于第二个值。）
条件三：如果数字大于第二个值，则返回true。
（此时两个值一定都被更新过了，满足第一个值小于第二个值小于第三个值。）

注意：
更新first后，second不会更新，但是second的存在可以确保曾经存在first小于second。
如果此时数字大于second，则数组中存在Triplet Subsequence。

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int first = Integer.MAX_VALUE;
        int second = Integer.MAX_VALUE;
        
        for(int num : nums){
            if(num < first){
                first = num;
            }
            else if(num > first && num < second){
                second = num;
            }
            else if(num > second){
                return true;
            }   
        }
        return false;
    }
}

双向遍历，逐渐收紧搜索窗口。设置i，k两个指针分别在头尾。
当nums[j] <= nums[i]，则更新i指针为j。
当nums[j] >= nums[k]，则更新k指针为j。
如果找到符合条件的nums[i] < nums[j] < nums[k]则返回。

class Solution {
    public boolean increasingTriplet(int[] nums) {
        boolean flag = true;
        int i = 0;
        int k = nums.length -1 ;
        int j;
        int count = 1;
        
        while(i < k && i + count < k){
            if(flag){
                j = i + count;
                if(nums[i] >= nums[j]){
                    i = j;
                    count = 1;
                    flag = true;
                    continue;
                }
                else if(nums[j] < nums[k]){
                    return true;
                }
                flag = !flag;
            }
            else{
                j = k - count;
                if(nums[k] <= nums[j]){
                    k = j;
                    count = 1;
                    flag = true;
                    continue;
                }
                else if(nums[j] > nums[i]){
                    return true;
                }
                else{
                    count++;
                }
                flag = !flag;
            }
        }
        return false;
    }
}