最长递增子序列
动态规划
-
解题思路：
- 使用数组 dp 保存每步子问题的最优解；
- dp[i] 代表含第 i 个元素的最长上升子序列的长度；
- 求解 dp[i] 时，向前遍历找出比 i 元素小的元素 j，令 dp[i] 为 max（dp[i],dp[j]+1)；
-
复杂度：
- 时间复杂度：O(n^2)；
- 空间复杂度：O(n)；
-
代码实现：
var lengthOfLIS = function (nums) { let n = nums.length; if (n === 0) return 0; //使用数组 dp 保存每步子问题的最优解 let dp = new Array(n).fill(1); for (let i = 0; i < n; i++) { for (let j = 0; j < i; j++) { if (nums[i] > nums[j]) { // dp[i] 代表含第 i 个元素的最长上升子序列的长度 dp[i] = Math.max(dp[i], dp[j] + 1); } } } return Math.max(...dp); };
贪心+二分
-
解题思路：
- 准备 tail 数组存放最长上升子序列，核心思想就是越小的数字越要往前放，这样后面就会有更多的数字可以加入tails 数组；
- 当 nums 中的元素比 tail 中的最后一个大时，可以放心push进tail；
- 否则进行二分查找，让比较小的数二分查找到合适的位置，让后面有更多的数字与这个数形成上升子序列；
-
复杂度：
- 时间复杂度：O(nlogn)；
- 空间复杂度：O(n)；
-
代码实现：
var lengthOfLIS = function (nums) { let n = nums.length; if (n <= 1) { return n; } //存放最长上升子序列数组 let tail = [nums[0]]; for (let i = 0; i < n; i++) { //当nums中的元素比tail中的最后一个大时 可以放心push进tail if (nums[i] > tail[tail.length - 1]) { tail.push(nums[i]); } else { //否则进行二分查找 let left = 0; let right = tail.length - 1; while (left < right) { let mid = (left + right) >> 1; if (tail[mid] < nums[i]) { left = mid + 1; } else { right = mid; } } //将nums[i]放置到合适的位置，此时前面的元素都比nums[i]小 tail[left] = nums[i]; } } return tail.length; };
扫码领红包
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 151. 颠倒字符串中的单词
上一篇
评论
