leetcode 334. 递增的三元子序列

leetcode 334. 递增的三元子序列

题目地址
题意：找三元组使其下标和数值都严格递增。要求时间复杂度 O(n) ，空间复杂度 O(1).
思路：直接说做法，定义两个变量 first 和 second，要求初始化时 first < second 且 first对应的值所在位置在 second 左边。然后从 second 所在位置往后遍历，按以下策略更新

遇到大于 second的数直接返回 true否则遇到小于 first 的数则更新 first否则遇到小于 second 的数则更新 second。

第一个和第三个应该还是比较好理解的，就是单纯的贪心让 second 尽量小，遇到比 second 大的就是合法的。比较有问题的是第二个，这里把 first 更新了会导致 first 在second 右边，但实际上虽然 first 变化了，但在 second 之前一定存在一个 first’，它是小于second 的，所以当我们遇到大于 second 的值，即使当前 first 在second 右边，也是合法的，因为我们不需要知道 first 具体是哪个。

class Solution {
public:
    bool increasingTriplet(vector& nums) {
        if((int)nums.size()<3) return false;
        int n=(int)nums.size();
        int f=nums[0];
        int s;
        int i;
        for(i=1;if){s=nums[i];break;}
        }
     //   cout<s) return true;
            else if(nums[i]f) s=nums[i];
        }
        return false;

    }
};