题目描述
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
- 输入：nums = [10,9,2,5,3,7,101,18]
- 输出：4
- 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
- 输入：nums = [0,1,0,3,2,3]
- 输出：4
示例 3：
- 输入：nums = [7,7,7,7,7,7,7]
- 输出：1
提示：
1 <= nums.length <= 2500- -104 <= nums[i] <= 104
进阶：
- 你能将算法的时间复杂度降低到
O(n log(n)) 吗？
解法一：动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
func max(nums ...int) int {
res := nums[0]
for _, val := range nums {
if val > res {
res = val
}
}
return res
}
func lengthOfLIS(nums []int) int {
n := len(nums)
dp := make([]int, n)
// dp[i] 表示在区间 nums[0...i] 中以 nums[i] 结尾的最长严格递增子序列的长度
dp[0] = 1
ans := 1
for i := 1; i < n; i++ {
dp[i] = 1
for j := 0; j < i; j++ {
if nums[i] > nums[j] {
dp[i] = max(dp[i],dp[j]+1)
}
}
ans = max(dp[i], ans)
}
return ans
}
|
解法二：贪心 + 二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
func max(nums ...int) int {
res := nums[0]
for _, val := range nums {
if val > res {
res = val
}
}
return res
}
func lengthOfLIS(nums []int) int {
n := len(nums)
var arr []int
arr = append(arr, nums[0])
for i := 1; i < n; i++ {
if nums[i] > arr[len(arr)-1] {
arr = append(arr, nums[i])
}
left, right := 0, len(arr)-1
for left <= right {
mid := left + (right-left)/2
if arr[mid] >= nums[i] {
right = mid - 1
} else {
left = mid + 1
}
}
arr[left] = nums[i]
}
return len(arr)
}
|
