从零学算法334

334.给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i < j < k 的三元组都满足题意
示例 2：
输入：nums = [5,4,3,2,1]
输出：false
解释：不存在满足题意的三元组
示例 3：
输入：nums = [2,1,5,0,4,6]
输出：true
解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6

• 我的原始人解法：题意我可以理解为，有一个数，存在它前面的某个数小于它，它后面的某个数大于它，就能返回 true
• 从第二个数往后遍历，因为只要之前存在某个数小于它即可，所以随遍历记录前面的最小值即可，这个实现很简单
• 实现了一半了。同理因为只需满足后面的某个数大于它，所以我们要得到对当前数来说，后面所有数中的最大值，这里我们用一个 map 存储 nums 中下标 i 对应的后面所有数的最大值是多少，也就是 map<i, max(nums[i+1]~nums[length-1])>。我们逆序遍历 nums，对 i 的前一位来说，它后面的最大值要么是新出现的 nums[i]，要么是之前得到的最大值，也就是 max(nums[i+1]~nums[length-1])，发现没，这其实就是 map.get(i)。

•   public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        if(n<3)return false;
        Map<Integer,Integer> map = new HashMap<>();
        // 最少要三个数，所以首尾的数我们都跳过判断
        // 对 n-2 来说他后面只有 nums[n-1]，所以初始化它得到最初的 max(nums[i+1]~nums[length-1])
        map.put(n-2,nums[n-1]);
        for(int i=n-2;i>1;i--){
            map.put(i-1,Math.max(map.get(i), nums[i]));
        }
        for(int i=1;i<n-1;i++){
            if(nums[i]>nums[i-1] && nums[i]<map.get(i))return true;
            // 为了省点空间直接不断更新 nums[i-1] 为前面所有数的最小值
            nums[i] = Math.min(nums[i],nums[i-1]);
        }
        return false;
    }
  

• 他人题解：其实只需要两个变量记录最小值 min 和次小值 mid 即可，先初始化他们为 Integer.MAX_VALUE，遍历 nums，如果一个数 num 大于 min，也大于 mid，就说明存在 min < mid < num 这样的序列，直接返回 true

•   public boolean increasingTriplet(int[] nums) {
        int min = Integer.MAX_VALUE, mid = Integer.MAX_VALUE;
        for(int num : nums){
            if(num <= min)min = num;
            // 走到这说明 min 肯定是被赋值了，即 min 存在的
            else if(num<=mid) mid=num;
            // 走到这说明 mid 也存在，那你大于 mid 就表示存在 min < mid < num
            else return true;
        }
        return false;
    }