###### tags: `LeetCode` `Medium`
# LeetCode #334 [Increasing Triplet Subsequence](https://leetcode.com/problems/increasing-triplet-subsequence/)
### (Medium)
給你一個整數數組 nums ，判斷這個數組中是否存在長度為 3 的遞增子序列。
如果存在這樣的三元組下標 (i, j, k) 且滿足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否則，返回 false 。

---
建立一數組作為回傳答案的容器, 當遍歷到的值大於數組末尾時, 將該數加入數組末端, 而若有值小於數組內的數, 則找到數組中第一個大於等於該數的數並將其取代(雖然順序不對, 但不影響結果, 因為小於數組末端的數的數量還是一樣, 取代的目的是為了以後若有其他數需要插入, 可降低數組的高度, 即便數組的長度不變)。

當回傳答案的數組長度等於3時, 回傳True。

---

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        vector<int> q;
        for(auto &a:nums){
            if(q.empty()||a>q.back())q.push_back(a);
            else{
                auto it = lower_bound(q.begin(),q.end(),a);
                *it=a;
            }
            if(q.size()==3)return 1;
        }
        return 0;
    }
};