题目说明
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
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
- -10^4 <= nums[i] <= 10^4
Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?
题目分析
这个问题也即LIS，解决方式是维护一个dp数组，对于nums[i]，找到nums[i]在dp中的lower_bound，即不小于nums[i]的第一个数的位置。如果找到了，则将dp中该元素替换为nums[i]；如果未找到，说明dp数组中每一个元素都小于nums[i]，此时将nums[i]添加到dp数组末尾即可。在查找lower_bound的过程中使用二分查找提高效率
注意 这个方法求解的是LIS的长度，dp中保存的不一定是最长递增子序列；比如以下例子
对于序列[2, 3, 1]
按照这个方法求解出来的dp数组，最终保存的是 [1, 3]; 明显不符合
示例代码
func lengthOfLIS(nums []int) int {
dp := []int{nums[0]}
for i := 1; i < len(nums); i++ {
// find lower bound of nums[i]
l, r := 0, len(dp)
for l < r {
mid := l + (r-l)/2
if dp[mid] >= nums[i] {
r = mid
} else {
l = mid + 1
}
}
if r == len(dp) {
dp = append(dp, nums[i])
} else {
dp[r] = nums[i]
}
}
return len(dp)
}