334. 递增的三元子序列

题目

题解

• i、j、k 可以不连续，所以不能够使用滑动窗口
• $O(n)$ ，空间复杂度为 $O(1)$ 表示只能遍历一次
• 假设 first 和 second 是有序的，且开始 first < second，依次遍历，获得 third
  • 如果 third 大于 second，说明满足条件 first < second < third，直接返回
  • 否则看 third 落在哪个区间
    • first < third，则对 second 进行赋值为 third，这样后续遍历 third > second 就会满足条件
    • first > third，则将 first 进行赋值为 third，因为在数组中肯定有比 second 小的数

class Solution {
    public boolean increasingTriplet(int[] nums) {

        if (nums.length < 3) {
            return false;
        }

        int first = nums[0];
        int second = Integer.MAX_VALUE;
        
        for (int i = 1; i < nums.length; i++) {
            int third = nums[i];

            if (third > second) {
                return true;
            }

            if (first < third) {
                second = third;
            } else {
                first = third;
            }
            
        }

        return false;
    }
}