|
16 | 16 |
|
17 | 17 | */ |
18 | 18 | publicclass_354 { |
19 | | -/**reference: https://discuss.leetcode.com/topic/47469/java-nlogn-solution-with-explanation*/ |
20 | | -publicintmaxEnvelopes(int[][]envelopes) { |
21 | | -if (envelopes ==null ||envelopes.length ==0 |
| 19 | +publicstaticclassSolution1 { |
| 20 | +/** reference: https://discuss.leetcode.com/topic/47469/java-nlogn-solution-with-explanation */ |
| 21 | +publicintmaxEnvelopes(int[][]envelopes) { |
| 22 | +if (envelopes ==null ||envelopes.length ==0 |
22 | 23 | ||envelopes[0].length ==0 ||envelopes[0].length !=2) { |
23 | | -return0; |
24 | | - } |
25 | | -Arrays.sort(envelopes, (int[]a,int[]b) -> { |
| 24 | +return0; |
| 25 | +} |
| 26 | +Arrays.sort(envelopes, (int[]a,int[]b) -> { |
26 | 27 | if (a[0] ==b[0]) { |
27 | 28 | returnb[1] -a[1]; |
28 | 29 | }else { |
29 | 30 | returna[0] -b[0]; |
30 | 31 | } |
31 | 32 | } |
32 | | - ); |
33 | | -int[]dp =newint[envelopes.length]; |
34 | | -intlen =0; |
35 | | -for (int[]envelope :envelopes) { |
36 | | -intindex =Arrays.binarySearch(dp,0,len,envelope[1]); |
37 | | -if (index <0) { |
38 | | -index = -(index +1); |
39 | | - } |
40 | | -dp[index] =envelope[1]; |
41 | | -if (index ==len) { |
42 | | -len++; |
| 33 | + ); |
| 34 | +int[]dp =newint[envelopes.length]; |
| 35 | +intlen =0; |
| 36 | +for (int[]envelope :envelopes) { |
| 37 | +intindex =Arrays.binarySearch(dp,0,len,envelope[1]); |
| 38 | +if (index <0) { |
| 39 | +index = -(index +1); |
| 40 | + } |
| 41 | +dp[index] =envelope[1]; |
| 42 | +if (index ==len) { |
| 43 | +len++; |
| 44 | + } |
43 | 45 | } |
| 46 | +returnlen; |
44 | 47 | } |
45 | | -returnlen; |
46 | 48 | } |
47 | 49 | } |