Leetcode--Java--334. 递增的三元子序列

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i < j < k 的三元组都满足题意
示例 2：

输入：nums = [5,4,3,2,1]
输出：false
解释：不存在满足题意的三元组

贪心 + 二分优化版 + 分类讨论

1. 在枚举过程中维护长度为2的递增序列，只要能存在长度为3的递增序列就成功。有点类似于维护一个单调队列，每次首先判断与队尾元素的大小关系。
2. 维护时，根据当前数和最小以及末尾数的关系，比末尾数大就直接加入到后面，否则分情况考虑：因为只要找到3就成功。所以只考虑长度为1或者2的情况。进行比较，小于最小的数，就更新最小的数，否则就更新末尾的数。
3. 该题目是AcWing之LC300二分法版本的简化版，不需要真正去二分，只考虑长度为2的直接判断即可。
4. linkedList设置某个index的数为num，直接用set(index, num)

class Solution {
    public boolean increasingTriplet(int[] nums) {
      linkedList l = new linkedList<>();
      for (int num: nums) {
        //空的话或者当前元素比末尾元素大就加入
          if (l.isEmpty() || num > l.peekLast()) {
               l.add(num);
               if (l.size() == 3) return true;
          }
          else {
              //分情况考虑，长度为1/2
              if (l.size() == 1){
                  l.set(0, num);
              }else if (l.size() == 2) {
                  //如果比最小的小，就更新最小（反正对结果序列没影响，因为核心是末尾元素）
                 if (num < l.get(0)) {
                     l.set(0, num);
                 }  //大于最小，由前面小于末尾，所以就成为新的末尾 
                 else if (num > l.get(0)) {
                      l.set(1, num);
                 }
              }
          }
      }
      return false;
    }
}