1、題目
image.png
2厦章、分析
這個問題也是最長子序列的問題。
具體分析可以參考：
https://labuladong.github.io/zgnb/3/15/17/
這里需要注意自定義數(shù)組排序的應(yīng)用，還有二分查找法的使用
3援所、代碼
class Solution {
public int maxEnvelopes(int[][] envelopes) {
//排序
Arrays.sort(envelopes, new Comparator<int[]>(){
public int compare(int[] a, int[] b){
return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
}
});
int[] heigth = new int[envelopes.length];
for(int i = 0; i < envelopes.length; i ++){
heigth[i] = envelopes[i][1];
}
//計算最長子序列
return lengthOfLIS(heigth);
}
private int lengthOfLIS(int[] nums){
int piles = 0;
int[] top = new int[nums.length];
for(int i = 0; i < nums.length; i++){
int poker = nums[i];
int left = 0;
int rigth = piles;
while(left < rigth){
int mid = (left + rigth) / 2;
if(top[mid] >= poker)
rigth = mid;
else
left = mid + 1;
}
if(left == piles) piles++;
top[left] = poker;
}
return piles;
}
}
