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

本文主要是介绍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)

代码

这篇关于Leetcode--Java--334. 递增的三元子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---