数组

优化技巧：

• 使用哈希做优化

题目：

1.前缀和

2.区间合并

function merge(list){
    list.sort((a,b)=>a[0]-b[0])//先按照每个区间的start位置排序
  let res = []
  res.push(list[0])
  for(let i=1;i<list.length;i++){
      let cur = list[i]
    let last = res[res.length-1]
    if(cur[0]<last[1]){
        last[1] = Math.max(last[1],cur[1])
    }else{
        res.push(cur);
    }
  }
  return res;
}

3.区间交集

function intervalSection(a,b){
    let i=0,j=0,res=[];
  while(i<a.length&&j<b.length){
      const ai = a[i],bj=b[j];
    if(b2>=a1&&a2>=b1){//存在交集的条件
      //具体交集区间的计算
        res.push([Math.max(ai[0],bj[0]),Math.min(ai[1],bj[1])])
      //指针的前进规则
      if(b2>a2){j++;}else{ i++;}
    }
  }
  return res;
}

4.二维数组（FloodFill算法）

5.最长递增子序列（动态规划/扑克牌二分法）

function maxEnvelops(envelops){
    const len = envelops.length;
  envelops.sort((a,b)=>{
      return a[0]===b[0]?(b[1]-a[1]):(a[0]-b[0]);
  });
  let heights = [];
  for(let i=0;i<len;i++){
      heights[i] = envelops[i][1];
  }
  return lengthOfLTS(heights);
}
// 放扑克牌方式，解释二分法
/* 返回 nums 中 LIS 的长度 */
public int lengthOfLIS(int[] nums) {
    int piles = 0, n = nums.length;
    int[] top = new int[n];
    for (int i = 0; i < n; i++) {
        // 要处理的扑克牌
        int poker = nums[i];
        int left = 0, right = piles;
        // 二分查找插入位置
        while (left < right) {
            int mid = (left + right) / 2;
            if (top[mid] >= poker)
                right = mid;
            else
                left = mid + 1;
        }
        if (left == piles) piles++;
        // 把这张牌放到牌堆顶
        top[left] = poker;
    }
    // 牌堆数就是 LIS 长度
    return piles;
}