🌕🌕🌕 334. 递增的三元子序列

难度: 🌕🌕🌕

问题描述

---

解法

class Solution {
    public boolean increasingTriplet(int[] nums) {
        // 思路：
        // 最先想到的是 最长递增序列 那道题，若牌堆数 >= 3 就可以直接返回，但是这样复杂度为 O(NlogN)
        // 这道题可以降低复杂度，无需遍历牌堆找到插入位置，因为 最多只有 2 个牌堆，通过只保存 前 2 个牌堆的最小值，一次遍历即可
        int len = nums.length;
        if(len < 3) {
            return false;
        }
        int first = nums[0]; // 三个数中的最小值，下标值也是三个中最小的
        int second = -1;
        boolean flag = false; // 表示第二个数还没有找到合适的
        for(int i = 1; i < len; i ++) {
            int cur = nums[i];
            // System.out.println(first + " : " + second + "  " + cur);
            // 最希望的情况是 first & second 均已找到，且 cur 满足 cur > second
            if(flag && cur > second) {
                return true; //相当于在原有 2 个牌堆的基础上新建一个牌堆，达到 3 个牌堆，直接返回
            } 
            // 判断新的牌的插入位置
            if(cur <= first) {
                first = cur;
            } else {
                // 插入第二个牌堆
                second = cur;
                flag = true;
            }
        }
        return false;
    }
}

---

输出