LC354. Russian Doll Envelopes
You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.
俄罗斯套娃信封。一开始想重写Arrays.sort( ), 不过想了一下应该是有bug，果然有。用DPsolution的话，首先对宽递增排列，如果遇到宽相同的信封，那么就把长比较长的放在前面。
看了discuss的解法发现这就是那个最长递增子序列问题当时一直不明白的Arrays.binarySearch( )函数终于明白了。所以简单DP的话用O(n^2)是可解的。如果用Binary Search的方法，复杂度就是O(nlgn).
Arrays.binarySearch( ) 的用法
Arrays.binarySearch(Object[] arr, Object key)函数通过二分查找的方式在啊arr中寻找可比较的元素key， 如果找到就返回元素所在位置下标，如果key不存在在arr中返回-(key如果存在应该在的位置下标，即key插入位置下标)-1. 所以arr要求以升序排序。例如key < arr[0], 则返回-1。
Binary Search Solution：
根据上面的规则重写compare，对每个信封进行二分查找，不断加入到dp的队列中，如果队列的长度增加则res增加。
public class Solution {
public int maxEnvelopes(int[][] envelopes) {
if(envelopes == null || envelopes.length == 0) return 0;
Arrays.sort(envelopes, new Comparator<int[]>(){
public int compare(int[] a, int[] b) {
if(a[0] == b[0]) return b[1] - a[1];
else return a[0] - b[0];
}
});
int[] dp = new int[envelopes.length];
int res = 0;
for(int[] envelope: envelopes){
int index = Arrays.binarySearch(dp, 0, res, envelope[1]);
if(index < 0) index = -index - 1;
dp[index] = envelope[1];
if(index == res) res++;
}
return res;
}
}
⚠️： 为了尽可能得到最优解，在宽度相同时把高度较大的放在前面。👇这个解释很好。
For anyone (like me) wondering why this algorithm uses its sorting scheme, consider its action on the following set of envelopes:
[[4,5],[4,6],[6,7],[2,3],[1,1]]Sort width ascending, then height descending for ties (accepted):
[[1, 1], [2, 3], [4, 6], [4, 5], [6, 7]] Searching for height of 1 Result of search: -1 Inserting height at index: 0 1 0 0 0 0 l is now 1 Searching for height of 3 Result of search: -2 Inserting height at index: 1 1 3 0 0 0 l is now 2 Searching for height of 6 Result of search: -3 Inserting height at index: 2 1 3 6 0 0 l is now 3 Searching for height of 5 Result of search: -3 Inserting height at index: 2 1 3 5 0 0 l is now 3 Searching for height of 7 Result of search: -4 Inserting height at index: 3 1 3 5 7 0 l is now 4 Max number of envelopes: 4Sort width ascending, then height ascending for ties:
[[1, 1], [2, 3], [4, 5], [4, 6], [6, 7]] Searching for height of 1 Result of search: -1 Inserting height at index: 0 1 0 0 0 0 l is now 1 Searching for height of 3 Result of search: -2 Inserting height at index: 1 1 3 0 0 0 l is now 2 Searching for height of 5 Result of search: -3 Inserting height at index: 2 1 3 5 0 0 l is now 3 Searching for height of 6 Result of search: -4 Inserting height at index: 3 1 3 5 6 0 l is now 4 Searching for height of 7 Result of search: -5 Inserting height at index: 4 1 3 5 6 7 l is now 5 Max number of envelopes: 5No sorting:
[[4, 5], [4, 6], [6, 7], [2, 3], [1, 1]] Searching for height of 5 Result of search: -1 Inserting height at index: 0 5 0 0 0 0 l is now 1 Searching for height of 6 Result of search: -2 Inserting height at index: 1 5 6 0 0 0 l is now 2 Searching for height of 7 Result of search: -3 Inserting height at index: 2 5 6 7 0 0 l is now 3 Searching for height of 3 Result of search: -1 Inserting height at index: 0 3 6 7 0 0 l is now 3 Searching for height of 1 Result of search: -1 Inserting height at index: 0 1 6 7 0 0 l is now 3 Max number of envelopes: 3