334. 遞增的三元子序列

給你一個整數(shù)數(shù)組?nums?，判斷這個數(shù)組中是否存在長度為?3?的遞增子序列。

如果存在這樣的三元組下標?(i, j, k)?且滿足?i < j < k?，使得?nums[i] < nums[j] < nums[k]?，返回?true?；否則，返回?false?。

思路：

假設(shè)a<b<c，a，b，c構(gòu)成遞增三元子序列，則目的就是定住a，b找符合的c。

固定a，b的做法是對于每個進入的元素，若比a小，則a為進入的元素，若比a大則和b比，比b小則更新b，反之則找到了遞增的三元子序列。這樣做可以成功找到的原因是，每次更新a和b，使得ab盡可能的小，方便找大的元素。先和a比再和b比，嚴格規(guī)定了a，b的大小關(guān)系。對于找到的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;}
};