算法题：俄罗斯套娃信封问题
先排序：
我们先按信封的宽度从小到大排序，如果宽度相同，就按高度从大到小排。这一步很关键，因为这样可以防止宽度相同时，错误地将高度也按递增算进去。
比如信封[5,4], [5,2]，如果不把高度按降序排，两个[5, _]会互相干扰。排序后就是这样： 输入：[ [5,4], [6,4], [6,7], [2,3] ]
排序：[ [2,3], [5,4], [6,7], [6,4] ]转化为LIS问题：
现在只需要在排好序的信封高度中找最长递增子序列。因为宽度已经保证不会干扰了，问题就变成一维的了，简单多了。
来吧，上代码：
import java.util.Arrays;
public class RussianDollEnvelopes {
public int maxEnvelopes(int[][] envelopes) {
// 按宽度升序，如果宽度相同则按高度降序
Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
// 提取高度数组
int[] heights = new int[envelopes.length];
for (int i = 0; i < envelopes.length; i++) {
heights[i] = envelopes[i][1];
}
// 找高度数组的最长递增子序列
return lengthOfLIS(heights);
}
private int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int len = 0;
for (int num : nums) {
// 二分查找插入点
int index = Arrays.binarySearch(dp, 0, len, num);
if (index < 0) index = -(index + 1); // 转换为插入点
dp[index] = num;
if (index == len) len++; // 如果插入在最后，说明序列长度增加
}
return len;
}
public static void main(String[] args) {
RussianDollEnvelopes solver = new RussianDollEnvelopes();
int[][] envelopes = {{5,4}, {6,4}, {6,7}, {2,3}};
System.out.println("最多能套的信封数量是: " + solver.maxEnvelopes(envelopes));
}
}
排序的 Arrays.sort用了自定义 Comparator，先比宽度，再比高度。lengthOfLIS方法里用了动态规划+二分查找。每次在当前的递增子序列中找插入点。如果找不到合适位置就扩展序列。
Arrays.binarySearch负责查找插入点，效率是O(log n)。最后 dp数组长度就是最长递增子序列的长度。
O(n log n)，很香吧？🍕面试官看到这，肯定对你刮目相看。-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。
