题目描述
给你一个整数数组n u m s numsnums，判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标( i , j , k ) (i, j, k)(i,j,k)且满足i < j < k i < j < ki<j<k，使得n u m s [ i ] < n u m s [ j ] < n u m s [ k ] nums[i] < nums[j] < nums[k]nums[i]<nums[j]<nums[k]，返回t r u e truetrue。否则，返回f a l s e falsefalse
示例 1：
输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i < j < k 的三元组都满足题意
示例 2：
输入：nums = [5,4,3,2,1]
输出：false
解释：不存在满足题意的三元组
示例 3：
输入：nums = [2,1,5,0,4,6]
输出：true
解释：其中一个满足题意的三元组是 (1, 4, 5)，因为 nums[1] < nums[4] < nums[5]
算法原理
这道题属于贪心中的递增子序列问题，一般可以通过300. 最长递增子序列的方法来解决
和最长递增子序列不同的是，这道题只需要找到长度为3 33的递增子序列就可以了，意味着l a s t E l e m e n t lastElementlastElement数组的大小如果是3 33，就可以直接返回t r u e truetrue，并且遇见n u m s [ i ] nums[i]nums[i]时，也可以不用二分优化，因为查找n u m s [ i ] nums[i]nums[i]的插入位置最多遍历两个元素，优化与不优化时间是差不多的
除此之外，实际上我们并不需要使用一个数组，直接用变量a , b a, ba,b分别存储长度为1 11的递增子序列的最后一个元素，长度为2 22的递增子序列的最后一个元素，初始化它们为n u m s [ 0 ] ，﹢ ∞ nums[0]，﹢∞nums[0]，﹢∞，之后遍历n u m s numsnums，遇到n u m s [ i ] nums[i]nums[i]时：
- n u m s [ i ] > b nums[i] > bnums[i]>b，说明能放在b bb之后，长度为3 33的递增子序列存在，返回t r u e truetrue
- a < n u m s [ i ] < = b a < nums[i] <= ba<nums[i]<=b，说明放在b bb之后的数，也能放在n u m s [ i ] nums[i]nums[i]之后，且n u m s [ i ] nums[i]nums[i]之后还能放更多的数，更新长度为2 22的递增子序列的最后一个数，b = n u m s [ i ] b = nums[i]b=nums[i]
- n u m s [ i ] < = a nums[i] <= anums[i]<=a，说明放在a aa之后的数，也能放在n u m s [ i ] nums[i]nums[i]之后，且n u m s [ i ] nums[i]nums[i]之后还能放更多的数，更新长度为1 11的递增子序列的最后一个数，a = n u m s [ i ] a = nums[i]a=nums[i]
代码
classSolution{public:boolincreasingTriplet(vector<int>&nums){inta=nums[0],b=INT_MAX;for(inti=1;i<nums.size();++i){if(nums[i]>b){returntrue;}elseif(nums[i]>a)// nums[i] ∈ (a, b]{b=nums[i];}elseif(nums[i]<=a){a=nums[i];}}returnfalse;}};
