【Leetcode-每日一题】递增的三元子序列

递增的三元子序列
难度：中等

这里我的思路是存在递增的三元子序列的话，那么就存在
三元组 i < j < k，如果枚举中间位置 jj, 分别看 i < j 和 j

对于i < j，正向遍历数组，维护最小值，对于位置 i，表示[0,i]中的最小值。对于j < k，反向遍历数组，维护最大值，对于位置 i，表示[i,nums.length]中的最大值。
因此，遍历数组，考虑每一个位置 j，如果 nums[j]大于左边的 [0,i]中的最小值，小于右边的 [i,nums.length]中的最大值，即存在递增的三元子序列。
代码如下：

	public boolean increasingTriplet(int[] nums) {
        if (nums.length<3){
            return false;
        }
        int[] left = new int[nums.length];
        int[] right = new int[nums.length];
        left[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            left[i] = nums[i] 0; i--) {
            right[i] = nums[i]>right[i+1] ? nums[i]:right[i+1];
        }

        for (int i = 0; i < nums.length; i++) {
            if (left[i] 
执行结果：成功
 
 执行用时不理想，看看其他人的思路:
 a 始终记录最小元素，b 为某个子序列里第二大的数。
 接下来不断更新 a，同时保持 b 尽可能的小。
 如果下一个元素比 b 大，说明找到了三元组。
 代码如下：
 
	public boolean increasingTriplet1(int[] nums) {
        int a = Integer.MAX_VALUE; 
        int b = Integer.MAX_VALUE;
        for (int n: nums){
            if (n <= a) a = n;
            else if (n <= b) b = n;
            else return true;
        }
        return false;
    }
 
执行结果：成功