Increasing Triplet Subsequence

这题挺有意思，主要是要找出是否有3个元素递增，这3个元素的索引必须依次增加但是不要求临近。首先贴题目：

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k 
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.
Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Example 1:

Input: [1,2,3,4,5]
Output: true
Example 2:

Input: [5,4,3,2,1]
Output: false

这题的事件复杂度要求是O(N)，空间复杂度要求为O(1)，所以我们无法暴力搜索。这题可以简化为是否能找出第三个最小值。我们首先定义变量min1与min2，分别表示最小值，第二小值，然后依次遍历数组。假设遍历到的值是比min1和min2更小的值，那么我们更新min1的值；假设遍历到比min2还小的值，那么更新min2，更新的时候也代表了min1被更新过了，也就是之前肯定有数字比当前值更加小；当遍历到比min1和min2更大的数字的时候，就表示在当前值前已经存在了至少2个数比它更小了，于是就表示这个数组是满足条件的。下面贴代码：

bool increasingTriplet(vector<int>& nums) {
    int min1 = INT_MAX, min2 = INT_MAX;
    for (auto v : nums) {
        if (v <= min1 && v <= min2) {
            min1 = v;
        } else if (v <= min2) {
            min2 = v;
        } else {
            return true;
        }
    }
    return false;
}