最长递增子序列

Posted by Jason on Monday, April 13, 2020

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
}

相关系列

  1. 最长递增子序列的个数
  2. 俄罗斯套娃信封问题
  3. 递增的三元子序列
  4. 马戏团人塔
  5. 最长数对链

「真诚赞赏,手留余香」

Jason Blog

真诚赞赏,手留余香

使用微信扫描二维码完成支付


comments powered by Disqus