[LeetCode] 300. Longest Increasing Subsequence
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4
Example 3:
Input: nums = [7,7,7,7,7,7,7]
Output: 1
Constraints:
1 <= nums.length <= 2500
-104 <= nums[i] <= 104
Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?
最长递增子序列。
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路一 - dp
注意子序列 subsequence 和子串 substring 的不同,子序列 subsequence 是可以断开的,只要相对顺序是上升的即可。这个题有两种做法,一是动态规划,一是动态规划基础上的二分。Longest Increasing Subsequence (LIS) 也是一类常考的题型。
首先是动态规划。设 dp[i] 是以 nums[i] 为结尾的子序列的最大长度。首先初始化的时候,dp 数组的每一个元素都是 1,因为如果以当前元素为结尾,不看其他元素的话,子序列最大长度就是 1。
更新 dp 数组的方法是用双指针,用一个指针 i 去遍历 input 的时候,同时设置另一个指针 j 扫描 j - i 的范围,如果在 j - i 的范围中有数字 nums[j] < nums[i],则 dp[i] = Math.max(dp[i], dp[j] + 1)
最后要找的结果是 dp 数组中的最大值。动图帮助理解。
复杂度
时间O(n^2)
空间O(n)
代码
Java实现
1 |
|
思路二 - 在dp上的二分查找
dp 基础上的二分法。创建一个和 input 等长的 input 数组 dp,这个 dp 数组是我们维护的一个 tails 列表,其中每个元素 tails[k] 的值代表长度为 k + 1 的子序列尾部元素的值。
把第一个数字放入 dp 数组,从第二个数字开始,用二分法去找到这个数字应该被放入的位置。这里的 dp 数组记录的是实打实的数字,注意最后 dp 数组中的结果可能并不一定是一个正确的子序列,但是长度是对的。
遍历input,
- 如果遇到的数字比 DP 数组里面最大的数字还要大,就加到 DP 数组的末端,len++,这也是唯一扩大 DP 数组 size 的办法
- 如果遇到的数字小于 DP 数组中的最大数字,则需要将这个数字通过二分法的方式放到 DP 数组中他该存在的位置,但是只能替换,而不是插入。
- 举个例子,如果你现在有数组[1, 3, 5],当你遇到一个4的时候,你只有通过把 5 替换成 4,才有可能将数组的最大值变小,从而有机会在数组的最后加入更多的值
复杂度
时间O(nlogn)
空间O(n)
代码
Java实现
1 |
|