题目描述给你一个整数数组n u m s numsnums判断这个数组中是否存在长度为 3 的递增子序列。如果存在这样的三元组下标( i , j , k ) (i, j, k)(i,j,k)且满足i j k i j kijk使得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 truetruea n u m s [ i ] b a nums[i] banums[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]bnums[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]anums[i]代码classSolution{public:boolincreasingTriplet(vectorintnums){intanums[0],bINT_MAX;for(inti1;inums.size();i){if(nums[i]b){returntrue;}elseif(nums[i]a)// nums[i] ∈ (a, b]{bnums[i];}elseif(nums[i]a){anums[i];}}returnfalse;}};
