力扣本周每日一题回顾 456.132模式

本周力扣题目中等简单为主，后几天主要考察链表（中等难度），总体难度都不难，个人感觉周三的132模式这题解题比较巧妙，拓展思维，下面来分享解题思维。

题目：给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。

个人比较耿直，一开始就想到从1到n-1作为3，然后2边分左右有序列表（通过二分法插入删除和查找位置），具体步骤是
把当前nums[i]作为3，先找到右边小于3的最大的值作为，
然后左边则是第一个最小值，判断是不是小于找到的2，如果找到，则说明符合，返回true，不然到最后，return false。
代码如下：

    const len=nums.length;
    if(nums<3) return false;
    let left_sort=new sort_list(),right_sort=new sort_list();
    left_sort.insert(nums[0])
    for(let i=1;i<len;i++){
        right_sort.insert(nums[i]);
    }
    let crt_max;
    for(let i=1;i<len-1;i++){
          crt_max=nums[i];
          let min=left_sort.list[0];
          right_sort.remove(crt_max);
          if(min<crt_max){
              let end=right_sort.get_index(crt_max)
              if(end>0&& right_sort.list[end-1]>min){
                  return true;
              }
              else{
                   left_sort.insert(crt_max);
              }
                  
          }
          else{
               left_sort.insert(crt_max);
          }
    }
    return false;

};
//二分法插入
class sort_list {
    constructor(){
        this.list=[];
    }
    insert(val){
        let left=this.get_index(val);
        this.list.splice(left,0,val)
    }
    get_index(val){
        let left=0,right=this.list.length-1;
        while(left<=right){
            let min=Math.floor((left+right)/2);
            if(this.list[min]>=val){
                right=min-1;
            }
            else{
                left=min+1;
            }
        }
        return lefti
    }
    remove(val){
          let left=this.get_index(val);
          this.list.splice(left,1)
    }
}

提交是通过的，但是思路比较直接，但是时间和内存都比较低效，而且看题目提示，是有时间复杂度为 O(n)的解决方案的。看力扣官方题解，确实比较巧妙。下面试官网描述

下面说一下个人理解，
3的值从最右边开始遍历，2的话是比3小的最大的值，一开始设置成（-Number.MAX_SAFE_INTEGER）， 然后与1比较，1的话比较简单可以一开始遍历用动态存储成一个最小值数组。
关键是2的值，2的值是右边栈（有序数组）比3小的最大的值，算法的关键是当3的值改变时候，把右边单调栈小于3的值一个个pop出去，然后2的值是pop的最后一个（也就是最大一个值）。
一开始有一点想不通，如果3位置左移的时候，nums[i-1]<nums[i]的话，那么nums[i]会不会把属于nums[i-1]的2给pop掉了，事实上根本不会有这种情况，因为如果nums[i]不满足（1大于了nums[i]时候的2，nums[i-1]<nums[i]时候，1肯定也大于了nums[i-1]时候的2），那么nums[i-1]也不会满足情况。表述有点粗糙，下面代码

    const n = nums.length;
    const min_list=new Array(n).fill(0);
    min_list[0]=nums[0];
    let temp=0;
    while(++temp<n){
        //得到i最小值数组
         min_list[temp]=Math.min(min_list[temp-1],nums[temp]);
    }
    const candidate_k = [nums[n - 1]];//用来存储 右边序列的
    let max_k = -Number.MAX_SAFE_INTEGER;//2一开始的值

    for (let i = n - 2; i >= 0; --i) {
        if (min_list[i] < max_k) {//1小于2
            return true;
        }
        while (candidate_k.length && nums[i] > candidate_k[candidate_k.length - 1]) {
            //因为是有序递减的 所以 max_k是小于3的最大值
            max_k = candidate_k[candidate_k.length - 1];
            candidate_k.pop();//pop掉  减少计算量
        }
        //比nums[i]小的都干掉了，所以nums[i]是最小的，所以是列表是有序递减的
        if (nums[i] > max_k) {
            candidate_k.push(nums[i]);
        }
    }
    return false;
};

时间效率从150ms到了80ms，有明显提升，力扣还有第三种题解，是单调栈加上二分查找，有兴趣的可以试试。
题目链接：leetcode-cn.com/problems/13…
力扣官方题解链接：leetcode-cn.com/problems/13…

ps:第一次发文，比较粗糙，有错误请指正一下，包容包容。