TOC
题目
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。 你算法的时间复杂度应该为 O(n2) 。 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
思路
采用动态规划思想，动态公式 f(i) = max({j<i && num[i]>num[j]|f(j)} + 1。每次子循环都遍历i次，这样复杂度为 O(n*n)。因为递增子序列的有序性，可以考虑使用递增队列数据结构，然后二分法查询可以定位小于 num[i] 的索引位置 j 。
代码
/*
O(nlgn) 使用递增队列，二分法定位最大前缀
*/
func FirstGreaterNum(nums []int, numLen, target int) (idx int) {
right := numLen - 1
left := 0
for left <= right {
mid := (left + right) / 2
if target > nums[mid] {
left = mid + 1
} else {
right = mid - 1
}
}
idx = left
return
}
func lengthOfLIS(nums []int) (length int) {
numLen := len(nums)
sortNum := make([]int, numLen)
sortLen := 0
for _, num := range nums {
idx := FirstGreaterNum(sortNum, sortLen, num)
if length < idx+1 {
length = idx + 1
}
if length >= sortLen {
sortLen = length
}
sortNum[idx] = num
}
return
}
题目变种
最长递增序列个数
给定一个未排序的整数数组，找到最长递增子序列的个数。
示例 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。 注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence
func findNumberOfLIS(nums []int) (count int) {
lis := make([]int, len(nums))
cntLIS := make([]int, len(nums))
maxLen := 1
for i, num := range nums {
max := 0
for j := 0; j < i; j++ {
if nums[j] >= num {
continue
}
length := lis[j]
if max < length {
max = length
}
}
lis[i] = max + 1
if maxLen < max+1 {
maxLen = max + 1
}
cnt := 0
for j := 0; j < i; j++ {
if nums[j] >= num {
continue
}
if max == lis[j] {
cnt += cntLIS[j]
}
}
if cnt == 0 {
cnt += 1
}
cntLIS[i] = cnt
}
for i := 0; i < len(nums); i++ {
if maxLen == lis[i] {
count += cntLIS[i]
}
}
return
}
俄罗斯套娃
给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
说明:
不允许旋转信封。
示例:
输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出: 3
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/russian-doll-envelopes
type Envelopes [][]int
func (e Envelopes) Less(i, j int) bool {
first, second := e[i], e[j]
if first[0] > second[0] {
return false
}
if first[0] == second[0] && first[1] > second[1] {
return false
}
return true
}
func (e Envelopes) Len() int {
return len(e)
}
func (e Envelopes) Swap(i, j int) {
e[j], e[i] = e[i], e[j]
}
func maxEnvelopes(envelopes [][]int) (count int) {
es := Envelopes(envelopes)
sort.Sort(es)
lis := make([]int, es.Len())
for i := 0; i < es.Len(); i++ {
max := 0
for j := 0; j < i; j++ {
if es[j][0] < es[i][0] && es[j][1] < es[i][1] && max < lis[j] {
max = lis[j]
}
}
length := max + 1
if count < length {
count = length
}
lis[i] = length
}
return
}
相关系列
「真诚赞赏，手留余香」
真诚赞赏，手留余香
使用微信扫描二维码完成支付
comments powered by Disqus