forked from fishercoder1534/Leetcode
-
Notifications
You must be signed in to change notification settings - Fork 1
/
_354.java
37 lines (35 loc) · 1.19 KB
/
_354.java
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
30
31
32
33
34
35
36
37
package com.fishercoder.solutions;
import java.util.Arrays;
public class _354 {
public static class Solution1 {
/**
* reference: https://discuss.leetcode.com/topic/47469/java-nlogn-solution-with-explanation
*/
public int maxEnvelopes(int[][] envelopes) {
if (envelopes == null || envelopes.length == 0 || envelopes[0].length == 0 || envelopes[0].length != 2) {
return 0;
}
Arrays.sort(envelopes, (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 len = 0;
for (int[] envelope : envelopes) {
int index = Arrays.binarySearch(dp, 0, len, envelope[1]);
if (index < 0) {
index = -(index + 1);
}
dp[index] = envelope[1];
if (index == len) {
len++;
}
}
return len;
}
}
}