354. Russian Doll Envelopes
文章目录
354. Russian Doll Envelopes
题目链接:https://leetcode.com/problems...
和300. Longest Increasing Subsequence类似的题,这里变成两个量了,依然是patient sort+binary search的思路。这里先按一个方向排序,另外一个方向按降序再排,这样就可以binary search了。
public class Solution {
public int maxEnvelopes(int[][] envelopes) {
if(envelopes.length == 0 || envelopes[0].length == 0) return 0;
Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
int n = envelopes.length;
int[] dp = new int[n+1];
int idx = 0;
for(int[] envelope : envelopes) {
if(envelope[1] > dp[idx]) dp[++idx] = envelope[1];
else if(envelope[1] <= dp[0]) dp[0] = envelope[1];
else {
int i = Arrays.binarySearch(dp, 0, idx+1, envelope[1]);
if(i < 0) i = -(i + 1);
dp[i] = envelope[1];
}
}
return idx;
}
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论