300. 最长递增子序列 Longest Increasing Subsequence
给你一个整数数组 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-10^4 <= nums[i] <= 10^4
进阶：
- 你能将算法的时间复杂度降低到
O(n log(n))吗?
代码1：二分查找，时间复杂度 O(n log n)
package main import "fmt" func lengthOfLIS(nums []int) int { n := len(nums) if n == 0 { return 0 } d := make([]int, n+1) d[1] = nums[0] len := 1 for i := 1; i < n; i++ { if nums[i] > d[len] { len++ d[len] = nums[i] } else { l, r := 1, len pos := 0 for l <= r { mid := l + (r-l)/2 if d[mid] < nums[i] { pos = mid l = mid + 1 } else { r = mid - 1 } } d[pos+1] = nums[i] } } return len } func main() { nums := []int{10, 9, 2, 5, 3, 7, 101, 18} fmt.Println(lengthOfLIS(nums)) nums = []int{0, 1, 0, 3, 2, 3} fmt.Println(lengthOfLIS(nums)) nums = []int{7, 7, 7, 7, 7, 7, 7} fmt.Println(lengthOfLIS(nums)) }
输出：
4
4
1
代码2：动态规划，时间复杂度：O(n^2)
package main import "fmt" func lengthOfLIS(nums []int) int { n := len(nums) dp := make([]int, n) // 初始化 dp 数组 for i := 0; i < n; i++ { dp[i] = 1 } ans := 1 // 开始 dp for i := 1; i < n; i++ { for j := 0; j < i; j++ { if nums[j] < nums[i] { dp[i] = max(dp[i], dp[j]+1) } } ans = max(ans, dp[i]) } return ans } func max(x, y int) int { if x > y { return x } return y } func main() { nums := []int{10, 9, 2, 5, 3, 7, 101, 18} fmt.Println(lengthOfLIS(nums)) nums = []int{0, 1, 0, 3, 2, 3} fmt.Println(lengthOfLIS(nums)) nums = []int{7, 7, 7, 7, 7, 7, 7} fmt.Println(lengthOfLIS(nums)) }
2407. 最长递增子序列 II Longest Increasing Subsequence ii
给你一个整数数组 nums 和一个整数 k 。
找到 nums 中满足以下要求的最长子序列：
- 子序列 严格递增
- 子序列中相邻元素的差值 不超过
k。
请你返回满足上述要求的 最长子序列 的长度。
子序列 是从一个数组中删除部分元素后，剩余元素不改变顺序得到的数组。
示例 1：
输入：nums = [4,2,1,4,3,4,5,8,15], k = 3
输出：5
解释：
满足要求的最长子序列是 [1,3,4,5,8] 。
子序列长度为 5 ，所以我们返回 5 。
注意子序列 [1,3,4,5,8,15] 不满足要求，因为 15 - 8 = 7 大于 3 。
示例 2：
输入：nums = [7,4,5,1,8,12,4,7], k = 5
输出：4
解释：
满足要求的最长子序列是 [4,5,8,12] 。
子序列长度为 4 ，所以我们返回 4 。
示例 3：
输入：nums = [1,5], k = 1
输出：1
解释：
满足要求的最长子序列是 [1] 。
子序列长度为 1 ，所以我们返回 1 。
提示：
1 <= nums.length <= 10^51 <= nums[i], k <= 10^5
代码：二分查找
package main import "fmt" var mx []int // 全局变量 func updateTree(root, l, r, i, val int) { if l == r { mx[root] = val return } mid := (l + r) / 2 if i <= mid { updateTree(root*2, l, mid, i, val) } else { updateTree(root*2+1, mid+1, r, i, val) } mx[root] = max(mx[root*2], mx[root*2+1]) } func query(root, l, r, L, R int) int { if L <= l && r <= R { return mx[root] } ret := 0 mid := (l + r) / 2 if L <= mid { ret = query(root*2, l, mid, L, R) } if R > mid { ret = max(query(root*2+1, mid+1, r, L, R), ret) } return ret } func lengthOfLIS(nums []int, k int) int { up := 0 for _, x := range nums { if x > up { up = x } } mx = make([]int, 4*up) for _, x := range nums { if x == 1 { updateTree(1, 1, up, 1, 1) } else { L := x - k if L < 1 { L = 1 } ret := 1 + query(1, 1, up, L, x-1) updateTree(1, 1, up, x, ret) } } return mx[1] } func max(a, b int) int { if a > b { return a } return b } func main() { nums1 := []int{4, 2, 1, 4, 3, 4, 5, 8, 15} k1 := 3 fmt.Println(lengthOfLIS(nums1, k1)) nums2 := []int{7, 4, 5, 1, 8, 12, 4, 7} k2 := 5 fmt.Println(lengthOfLIS(nums2, k2)) nums3 := []int{1, 5} k3 := 1 fmt.Println(lengthOfLIS(nums3, k3)) }
输出：
5
4
1
673. 最长递增子序列的个数 Number of Longest Increasing Subsequence
给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
注意 这个数列必须是 严格 递增的。
示例 1:
输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
示例 2:
输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
提示:
1 <= nums.length <= 2000-10^6 <= nums[i] <= 10^6
代码：
package main import "fmt" func findNumberOfLIS(nums []int) int { n := len(nums) if n <= 1 { return n } dp := make([]int, n) cnt := make([]int, n) for i := range dp { dp[i], cnt[i] = 1, 1 } maxLen, ans := 1, 0 for i := 1; i < n; i++ { for j := 0; j < i; j++ { if nums[j] < nums[i] { if dp[j]+1 > dp[i] { dp[i], cnt[i] = dp[j]+1, cnt[j] } else if dp[j]+1 == dp[i] { cnt[i] += cnt[j] } } } maxLen = max(maxLen, dp[i]) } for i := range cnt { if dp[i] == maxLen { ans += cnt[i] } } return ans } func max(x, y int) int { if x > y { return x } return y } func main() { fmt.Println(findNumberOfLIS([]int{1, 3, 5, 4, 7})) fmt.Println(findNumberOfLIS([]int{2, 2, 2, 2, 2})) }
输出：
2
5
🌟 每日一练刷题专栏 🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
|
Rust每日一练 专栏 （2023.5.16~）更新中... |
|
Golang每日一练 专栏 （2023.3.11~）更新中... |
|
Python每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
C/C++每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
Java每日一练 专栏 （2023.3.11~2023.5.18）暂停更 |
