前言
hello world欢迎来到前端的新世界
😜当前文章系列专栏：前端面试
🐱👓博主在前端领域还有很多知识和技术需要掌握，正在不断努力填补技术短板。(如果出现错误，感谢大家指出)🌹
💖感谢大家支持！您的观看就是作者创作的动力
题目
用js实现一个整数数组nums，找到其中最长严格递增子序列的长度，子序列是由数组派生而来的序列，删除(或不删除)数组中的元素而不改变其余元素的顺利，例如[3,0,2,7]是数组的[0,3,1,6,2,2,7]
加分项 :把算法难度降到O(nlog(n))
代码
方法一，二分查找法
function lengthOfLIS(nums) { // 特殊情况处理 if (nums.length === 0) { return 0; } // 创建一个数组，用于存储递增子序列的末尾数 const tails = [nums[0]]; // 遍历数组，更新这个数组中的最长递增子序列 for (let i = 1; i < nums.length; i++) { // 如果当前数比递增子序列的末尾数大，则将当前数加入递增子序列末尾 if (nums[i] > tails[tails.length - 1]) { tails.push(nums[i]); } else { // 如果当前数比递增子序列的末尾数小，则用二分查找找到第一个比它大的数，并替换它 const left = 0, right = tails.length - 1; while (left < right) { const mid = Math.floor((left + right) / 2); if (tails[mid] < nums[i]) { left = mid + 1; } else { right = mid; } } tails[left] = nums[i]; } } // 最后，返回递增子序列的长度，即 tails 数组的长度 return tails.length; }
方法二，动态规划
function lengthOfLIS(nums) { const len = nums.length; if (len === 0) return 0; const dp = new Array(len); let res = 0; dp[0] = nums[0]; for (let i = 1; i < len; i++) { if (nums[i] < dp[0]) { dp[0] = nums[i]; // 替换掉最小末尾值 } else if (nums[i] > dp[res]) { dp[++res] = nums[i]; // 如果当前元素大于所有已有递增子序列的末尾值，则直接添加到末尾 } else { // 使用二分查找找到 nums[i] 在 dp 数组中该插入的位置，并替换掉该位置的值 let left = 0; let right = res; while (left < right) { const mid = Math.floor((left + right) / 2); if (dp[mid] < nums[i]) { left = mid + 1; } else { right = mid; } } dp[left] = nums[i]; } } return res + 1; }
后言
创作不易，要是本文章对广大读者有那么一点点帮助 不妨三连支持一下，您的鼓励就是博主创作的动力
