300.md

Leetcode 300. 最长递增子序列

300. 最长递增子序列

本题解法参考了 Patience Sorting，详情见花花酱 LeetCode 300 Longest Increasing Subsequence O(nlogn) - 刷题找工作 EP378

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
  let ret = [];
  ret[0] = nums[0]; // 将目标数组第一个数字塞入新数组 dp 中

  // 从目标数组第二个数字开始遍历
  for (let i = 1; i < nums.length; i++) {
    let current = nums[i]; // 当前处理的数字
    if (current > ret[ret.length - 1]) { // 如果 current 大于数组最后一个数字，将其推入到数组最后面
      ret.push(current);
    } else {
      // 通过二分查找，找出对应 current 应该写入的数组位置，即 current 比该下标前一个数字大。
      let left = 0;
      let right = ret.length - 1;
      while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (ret[mid] < current) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      ret[left] = current;
    }
  }
  return ret.length;
};

console.log(lengthOfLIS([3, 5, 6, 2, 5, 4, 19, 5, 6, 7, 12]));
console.log(lengthOfLIS([0, 1, 0, 3, 2, 3]));
console.log(lengthOfLIS([7, 7, 7, 7, 7, 7, 7]));
console.log(lengthOfLIS([4, 10, 4, 3, 8, 9]));
console.log(lengthOfLIS([10, 5, 8, 3, 9, 4, 12, 11]));