354. 俄罗斯套娃信封问题

Problem: 354. 俄罗斯套娃信封问题

文章目录

• 思路
• 解题方法
• 复杂度
• Code

思路

这个问题可以转换为最长递增子序列（Longest Increasing Subsequence，LIS）问题。先对信封按宽度升序排序，当宽度相同时，按高度降序排序。然后在排序后的信封数组中找到最长的严格递增的高度序列。

解题方法

首先对信封进行排序，接着使用动态规划的思想求解最长递增子序列。具体实现时，使用一个ends数组存储递增子序列的结尾元素，通过二分查找确定当前元素应该放置的位置。

复杂度

时间复杂度:

O

(

n

l

o

g

n

)

O(nlogn)

O(nlogn)，其中nn是信封的数量。主要开销来自于排序和二分查找。

空间复杂度:

O

(

n

)

O(n)

O(n)，用于存储排序后的信封数组和ends数组。

Code

class Solution {
public int maxEnvelopes(int[][] envelopes) {
int n = envelopes.length;
// 按照信封的宽度排序 如果宽度相同 按照高度从大到小排序
Arrays.sort(envelopes, (a, b) -> a[0] != b[0] ? (a[0] - b[0]) : (b[1] - a[1]));
// 根据高度LIS模板
int[] ends = new int[n];
int len = 0;
for (int i = 0, find; i < n; i++) {
find = bs(ends, len, envelopes[i][1]);
if (find == -1) {
ends[len++] = envelopes[i][1];
} else {
ends[find] = envelopes[i][1];
}
}
return len;
}
public int bs(int[] ends, int len, int num) {
int l = 0, r = len - 1, m, ans = -1;
while(l <= r) {
m = (l + r) / 2;
if(ends[m] >= num) {
ans = m;
r = m - 1;
} else {
l = m + 1;
}
}
return ans;
}
}