1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
List<Integer> tails = new ArrayList<>();
for (int[] envelop : envelopes) {
int targetIdx = binarySearch(tails, envelop[1]);
if (targetIdx + 1 == tails.size()) {
tails.add(envelop[1]);
} else {
tails.set(targetIdx + 1, envelop[1]);
}
}
return tails.size();
}
private int binarySearch(List<Integer> tails, int target) {
int left = 0, right = tails.size() - 1, ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (tails.get(mid) < target) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return ans;
}
}
|
有点儿类似找longest increasing sequence. 但是我们不一定非要按照给的envelop的相对顺序去一个装另一个. 而是可以选完后, 自己决定哪个装哪个. 于是我们就想到既然这样我们让width先递增排列. 这样从左到右width至少是非递减的. 由于width已经是递增, 此时跟据height就找LIS. 但是问题就在于相同width的envelop只能选一个. 比如[2, 3], [2, 4], [2, 5], 我们发现根据height找的LIS是3, 但其实这种情况没有其他的envelop能装其他的, 因此答案应该是1. 那么如何避免这种情况呢? 也就是构成LIS时避免选择相同的width. 一个聪明的做法就是把height倒序再排列. 这样构成的LIS中的任意两个元素肯定不可能来自相同的
width的envelop. 这样就变成了以height为准的LIS了.
时间复杂度: O(nlogn)
空间复杂度: O(n) 可能envelop一直是递增的, list存n个元素.
