# 0334. Increasing Triplet Subsequence
###### tags: `Leetcode` `Medium` `Array`
## 思路
非常tricky的一道题
之前想的办法是遍历的过程中，记录下来前面出现过的最小的数当作开头，如果碰到一个数比前面最小的数小，那么就开始遍历后面，看有没有比这个数大的数，有的话就回传true，但这个方法由于复杂度是O(N^2)，就TLE了
题目要找的是 **时间复杂度O（N），空间复杂度O(1)** 的

**正确思路：**
首先，新建两个变量 small 和 mid ，分别用来保存题目要我们求的长度为 3 的递增子序列的最小值和中间值。

接着，我们遍历数组，每遇到一个数字，我们将它和 small 和 mid 相比，若小于等于 small ，则替换 small；否则，若小于等于 mid，则替换 mid；否则，若大于 mid，则说明我们找到了长度为 3 的递增数组！

上面的求解过程中有个问题：当已经找到了长度为 2 的递增序列，这时又来了一个比 small 还小的数字，为什么可以直接替换 small 呢，这样 small 和 mid 在原数组中并不是按照索引递增的关系呀？

Trick 就在这里了！假如当前的 small 和 mid 为 [3, 5]，这时又来了个 1。假如我们不将 small 替换为 1，那么，当下一个数字是 2，后面再接上一个 3 的时候，我们就没有办法发现这个 [1,2,3] 的递增数组了！也就是说，我们替换最小值，是为了后续能够更好地更新中间值！

另外，即使我们更新了 small ，这个 small 在 mid 后面，没有严格遵守递增顺序，但它隐含着的真相是，有一个比 small 大比 mid 小的前·最小值出现在 mid 之前。因此，当后续出现比 mid 大的值的时候，我们一样可以通过当前 small 和 mid 推断的确存在着长度为 3 的递增序列。 所以，这样的替换并不会干扰我们后续的计算！

## Code in Java

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int small = Integer.MAX_VALUE,mid = Integer.MAX_VALUE;
        for(int num:nums){
            if(num<small) small = num;
            else if(small<num && num<mid) mid = num;
            else if(num>mid) return true;
        }
        return false;
    }
}

## Result
Runtime: 2 ms, faster than **64.10%** of Java online submissions for Increasing Triplet Subsequence.
Memory Usage: 80 MB, less than **98.40%** of Java online submissions for Increasing Triplet Subsequence.