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.
What is the maximum number of envelopes can you Russian doll? (put one inside other)
Example:
Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).
一刷
題解：
首先對(duì)數(shù)組根據(jù)width進(jìn)行排序, 如果width相同, height遞減
然后就變成了尋找longest increasing subsequence的子問(wèn)題则吟。注意，這個(gè)dp數(shù)組存儲(chǔ)遞增序列翘魄。
Time complexity O(nlogn), space complexity O(n)
public class Solution {
public int maxEnvelopes(int[][] envelopes) {
if(envelopes == null || envelopes.length == 0) return 0;
//Ascend on width and descend on height if width are same.
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];//first compare width
}
});
int[] dp = new int[envelopes.length];
int len = 0;
for(int[] envelope : envelopes){
int index = Arrays.binarySearch(dp, 0, len, envelope[1]);
if(index<0) index = -(index+1);//the insert point
dp[index] = envelope[1];//height
if(index == len) len++;
}
return len;
}
}
二刷：
注意蜓肆，為了不把[4,5], [4,6]算做一組有效的值掂榔，當(dāng)長(zhǎng)相等時(shí)，寬用逆序症杏。保證只有一個(gè)被算進(jìn)去装获。
排序后變?yōu)閇4,6],[4,5].
分析：怎樣用binarySearch找到需要insert的地方。用最典型的binarysearch的寫(xiě)法就能實(shí)現(xiàn)厉颤。因?yàn)檠ㄔィ詈笠粋€(gè)點(diǎn)的時(shí)候，i,j肯定相鄰逼友，mid處于i的地方精肃，如果大于i，則Insert的地方為j帜乞， 否則為i. 即滿足lo == hi的點(diǎn)司抱。但是注意dp的數(shù)組需要先f(wàn)ill Integer.MAX_VALUE
public class Solution {
public int maxEnvelopes(int[][] envelopes) {
int len = envelopes.length;
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[len];
Arrays.fill(dp, Integer.MAX_VALUE);
len = 0;
for(int[] env : envelopes){
int index = bs(dp, 0, len, env[1]);
dp[index] = env[1];
if(index == len) len++;
}
return len;
}
public int bs(int[] dp, int lo, int hi, int target){
while(lo<=hi){
int mid = lo + (hi-lo)/2;
if(dp[mid] == target) return mid;
else if(dp[mid]<target) lo = mid+1;
else hi = mid-1;
}
return lo;
}
}
三刷
題解：有兩個(gè)需要特別注意的地方
一個(gè)是sort的時(shí)候，如果根據(jù)width排序黎烈，如果width相等习柠，height高的在前匀谣。
一個(gè)是dp數(shù)組初始化的時(shí)候要Arrays.fill(dp, Integer.MAX_VALUE), 這樣才能用binarySearch找到正確的位置。
class Solution {
public int maxEnvelopes(int[][] envelopes) {
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];
}
});
//longest ascending subsequence
int len = 0;
int[] res = new int[envelopes.length];
Arrays.fill(res, Integer.MAX_VALUE);
for(int i=0; i<envelopes.length; i++){
int height = envelopes[i][1];
int index = Arrays.binarySearch(res, height);
if(index<0) index = -(index+1);
if(index == len) len++;
res[index] = height;
}
return len;
}
}
