【2022-09-03每日一题】646. 最长数对链
2022-09-03
2分钟阅读时长
2022-09-03每日一题：646. 最长数对链
- 难度：Medium
- 标签：贪心 、 数组 、 动态规划 、 排序
给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例：
输入：[[1,2], [2,3], [3,4]] 输出：2 解释：最长的数对链是 [1,2] -> [3,4]
提示：
- 给出数对的个数在
[1, 1000]范围内。
func findLongestChain(pairs [][]int) int {
sort.Slice(pairs, func(i, j int) bool { return pairs[i][0] < pairs[j][0] })
n := len(pairs)
dp := make([]int, n)
for i, p := range pairs {
dp[i] = 1 // 初始化时，dp 需要全部赋值为 1
for j, q := range pairs[:i] {
if p[0] > q[1] {
dp[i] = max(dp[i], dp[j] + 1)
}
}
}
return dp[n-1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
复杂度分析
时间复杂度：O(n^2)，其中 n 为 pairs 的长度。排序的时间复杂度为O(nlogn)，两层 for 循环的时间复杂度为 O(n^2)。
空间复杂度：O(n)，数组dp 的空间复杂度为 O(n)。
方法二：最长递增子序列【需要再度理解】
func findLongestChain(pairs [][]int) int {
sort.Slice(pairs, func (i, j int) bool {return pairs[i][0] < pairs[j][0] })
arr := []int{}
for _, p := range pairs {
i := sort.SearchInts(arr, p[0])
if i < len(arr) {
arr[i] = min(arr[i], p[1])
} else {
arr = append(arr, p[1])
}
}
return len(arr)
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
复杂度分析
时间复杂度：O(nlogn)，其中 nn 为 pairs 的长度。排序的时间复杂度为O(nlogn)，二分查找的时间复杂度为O(nlogn)，二分的次数为O(n)。
空间复杂度：O(n)，数组 arr 的长度最多为 O(n)。
方法三：贪心
思路
要挑选最长数对链的第一个数对时，最优的选择是挑选第二个数字最小的，这样能给挑选后续的数对留下更多的空间。挑完第一个数对后，要挑第二个数对时，也是按照相同的思路，是在剩下的数对中，第一个数字满足题意的条件下，挑选第二个数字最小的。按照这样的思路，可以先将输入按照第二个数字排序，然后不停地判断第一个数字是否能满足大于前一个数对的第二个数字即可。
代码
func findLongestChain(pairs [][]int) (ans int) {
sort.Slice(pairs, func (i, j int) bool { return pairs[i][1] < pairs[j][1] })
cur := math.MinInt32
for _, p := range pairs {
if cur < p[0] {
cur = p[1]
ans++
}
}
return ans
}
复杂度分析
时间复杂度：(nlogn)，其中 n 为 pairs 的长度。排序的时间复杂度为 O(nlogn)。
空间复杂度：O(logn)，为排序的空间复杂度。