最长数对链
难度:
标签:
题目描述
代码结果
运行时间: 54 ms, 内存: 16.5 MB
/*
* Solution in Java using Streams
*
* 思路：
* 1. 使用 Java Stream 进行排序。
* 2. 用 reduce 方法计算最长数对链。
*/
import java.util.Arrays;
public class SolutionStream {
public int findLongestChain(int[][] pairs) {
return Arrays.stream(pairs)
.sorted((a, b) -> Integer.compare(a[1], b[1]))
.reduce(new int[]{Integer.MIN_VALUE, 0},
(acc, pair) -> pair[0] > acc[0] ? new int[]{pair[1], acc[1] + 1} : acc,
(acc1, acc2) -> acc1)[1];
}
}
解释
方法:
此题解采用了贪心算法。首先，对输入的数对数组按照每个数对的第二个元素升序排序，如果第二个元素相同，则按第一个元素降序排序。这样可以优先处理右端点较小的数对，以便使得后续有更多的可能数对可以接上去。初始化一个计数器 cnt 和变量 last，分别用来记录最长链的长度和上一个数对的右端点。遍历排序后的数对，只有当当前数对的左端点大于 last 时，才能将其加入到当前的数对链中，此时更新 cnt 和 last。最后返回 cnt，即为最长数对链的长度。
时间复杂度:
O(n log n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在排序数对时选择按第二个元素升序排序，而在相同的第二元素情况下按第一个元素降序排序？
▷🦆
在题解中提到的贪心策略是基于什么理论或直觉？为什么选择这种策略可以得到最长的数对链？
▷🦆
如果数对数组中存在重复的数对，例如[[1,2],[1,2],[2,3]]，这种情况下算法是否还能正确运行？会有什么特别的处理吗？
▷🦆
题解中提到初始化cnt为1而不是0，这是基于什么考虑？
▷相关问题
最长递增子序列
给你一个整数数组 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))吗?