|
2 | 2 |
|
3 | 3 | importjava.util.Arrays; |
4 | 4 |
|
5 | | -/** |
6 | | - * 354. Russian Doll Envelopes |
7 | | - * |
8 | | - * You have a number of envelopes with widths and heights given as a pair of integers (w, h). |
9 | | - * One envelope can fit into another if and only if both the width and height of one envelope is greater than |
10 | | - * the width and height of the other envelope. |
11 | | -
|
12 | | - What is the maximum number of envelopes can you Russian doll? (put one inside other) |
13 | | -
|
14 | | - Example: |
15 | | - 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]). |
16 | | -
|
17 | | - */ |
18 | 5 | publicclass_354 { |
19 | 6 | publicstaticclassSolution1 { |
20 | | -/** reference: https://discuss.leetcode.com/topic/47469/java-nlogn-solution-with-explanation */ |
| 7 | +/** |
| 8 | + * reference: https://discuss.leetcode.com/topic/47469/java-nlogn-solution-with-explanation |
| 9 | + */ |
21 | 10 | publicintmaxEnvelopes(int[][]envelopes) { |
22 | 11 | if (envelopes ==null ||envelopes.length ==0 |
23 | | - ||envelopes[0].length ==0 ||envelopes[0].length !=2) { |
| 12 | +||envelopes[0].length ==0 ||envelopes[0].length !=2) { |
24 | 13 | return0; |
25 | 14 | } |
26 | 15 | Arrays.sort(envelopes, (int[]a,int[]b) -> { |
27 | | -if (a[0] ==b[0]) { |
28 | | -returnb[1] -a[1]; |
29 | | - }else { |
30 | | -returna[0] -b[0]; |
| 16 | +if (a[0] ==b[0]) { |
| 17 | +returnb[1] -a[1]; |
| 18 | + }else { |
| 19 | +returna[0] -b[0]; |
| 20 | + } |
31 | 21 | } |
32 | | - } |
33 | 22 | ); |
34 | 23 | int[]dp =newint[envelopes.length]; |
35 | 24 | intlen =0; |
|