网站在线演示wordpress 自定义链接地址

334. 递增的三元子序列

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

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

思路：

假设a<b<c，a，b，c构成递增三元子序列，则目的就是定住a，b找符合的c。

固定a，b的做法是对于每个进入的元素，若比a小，则a为进入的元素，若比a大则和b比，比b小则更新b，反之则找到了递增的三元子序列。这样做可以成功找到的原因是，每次更新a和b，使得ab尽可能的小，方便找大的元素。先和a比再和b比，严格规定了a，b的大小关系。对于找到的c，存在两种情况，一种是a更新了b没有更新，则可以视为用原来的a和b加上c。若a，b都是更新后的，则是用当前的a，b加上c。

class Solution {
public:bool increasingTriplet(vector<int>& nums) {int a=nums[0],b=INT_MAX;for(auto e:nums){   if(a>=e){a=e;}else if(b>=e){b=e;}elsereturn true;}return false;}
};