给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
示例 1：
输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
示例 2：
输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1
class Solution { public int maxEnvelopes(int[][] envelopes) { if (envelopes.length==0) return 0; //排下序，先第一维度升序，后第二维度降序 Arrays.sort(envelopes,(t1,t2)->{ if (t1[0] < t2[0]) return -1; else if (t1[0] == t2[0]) { if (t1[1] > t2[1]) return -1; else if (t1[1] == t2[1]) return 0; } return 1; }); //用动态规划去求解子问题 int[] dp=new int[envelopes.length]; Arrays.fill(dp,1); int max=1; for(int i=1;i<envelopes.length;i++){ for(int j=0;j<i;j++){ if(envelopes[i][1]>envelopes[j][1]) dp[i] = Math.max(dp[i], dp[j] + 1); } max = Math.max(max, dp[i]); } return max; } }
首先，排序问题，我找到了博客可以用Arrays.sort数组来写，发现自己又不是很熟悉，于是贴一下
Arrays.sort(int[] a, int fromIndex, int toIndex)
这种形式是对数组部分排序，也就是对数组a的下标从fromIndex到toIndex-1的元素排序，注意：下标为toIndex的元素不参与排序哦！
还有这种lamda表达式的方式，这是在java8里面出现的语法糖
https://www.cnblogs.com/goodshred/p/9882764.html
以下代码，是这个网址引用过来的，仅供自己学习和参考，
// 1. 不需要参数,返回值为 5 () -> 5 // 2. 接收一个参数(数字类型),返回其2倍的值 x -> 2 * x // 3. 接受2个参数(数字),并返回他们的差值 (x, y) -> x – y // 4. 接收2个int型整数,返回他们的和 (int x, int y) -> x + y // 5. 接受一个 string 对象,并在控制台打印,不返回任何值(看起来像是返回void) (String s) -> System.out.print(s) String[] atp = {"Rafael Nadal", "Novak Djokovic", "Stanislas Wawrinka", "David Ferrer","Roger Federer", "Andy Murray","Tomas Berdych", "Juan Martin Del Potro"}; List<String> players = Arrays.asList(atp); // 以前的循环方式 for (String player : players) { System.out.print(player + "; "); } // 使用 lambda 表达式以及函数操作(functional operation) players.forEach((player) -> System.out.print(player + "; ")); // 在 Java 8 中使用双冒号操作符(double colon operator) players.forEach(System.out::println); String[] players = {"Rafael Nadal", "Novak Djokovic", "Stanislas Wawrinka", "David Ferrer", "Roger Federer", "Andy Murray", "Tomas Berdych", "Juan Martin Del Potro", "Richard Gasquet", "John Isner"}; // 1.1 使用匿名内部类根据 name 排序 players Arrays.sort(players, new Comparator<String>() { @Override public int compare(String s1, String s2) { return (s1.compareTo(s2)); } }); // 1.2 使用 lambda expression 排序 players Comparator<String> sortByName = (String s1, String s2) -> (s1.compareTo(s2)); Arrays.sort(players, sortByName); // 1.3 也可以采用如下形式: Arrays.sort(players, (String s1, String s2) -> (s1.compareTo(s2)));
这是二维数组中的拉姆达表达式里面的
对后面题目是有帮助的
回到正题：
题目思路是：先对宽排序，然后再对第二维的长求最长子序列（不了解可以看上一篇文章）