题目

题目链接：
https://www.nowcoder.com/practice/9bf77b5b018d4d24951c9a7edb40408f

相同的题目：
https://www.lintcode.com/problem/602

思路

	本质是求最长子序列问题envelopes 先按 w 升序排序，再按 h 降序 排序，只需考虑h即可，因为w已经升序排列好，因为h大的在前，所以相同的w下的不同h，只会选择最大的那个h。就可以将问题转换为 h 的 Longest Increasing subSequence对参数长度升序，宽度降序排序因为长度和宽度都要大于才能装进去比如：int[][] arr = {{5,4},{6,4},{6,7},{2,3}};//2,3  5,4  6,7  6,4求的就是 3 4 7 4  最长递增子序列问题

参考答案Java

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param letters int整型二维数组* @return int整型*/public int maxLetters (int[][] letters) {Arrays.sort(letters, new Comparator<int[]>() { //长升序，长相同，宽降序@Overridepublic int compare(int[] a, int[] b) {if(a[0] !=b[0]){return a[0]-b[0];}else{return b[1]-a[1];}}});int[] dp = new int[letters.length];Arrays.fill(dp,1);//宽度 最长上升子序列问题int ans = 1;for (int i = 0; i <letters.length ; i++) {for (int j = i-1; j >=0 ; j--) {if(letters[j][1]<letters[i][1]){dp[i] = Math.max(dp[i],dp[j]+1);}ans =Math.max(dp[i],ans);}}return ans;}
}

参考答案Go

package main
import "sort"/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param letters int整型二维数组* @return int整型*/
func maxLetters(letters [][]int) int {//本质是最递增子序列问题//长度升序，相同长度，宽度降序sort.Slice(letters, func(i int, j int) bool {if letters[i][0] != letters[j][0] {return letters[i][0] < letters[j][0]} else {return letters[i][1] > letters[j][1]}})//高度的最长上升子序列问题dp := make([]int, len(letters))ans := 1for i := 0; i < len(letters); i++ {dp[i] = 1for j := i - 1; j >= 0; j-- {if letters[j][1] < letters[i][1] {cur := dp[j] + 1if cur > dp[i] {dp[i] = cur}if ans < dp[i] {ans = dp[i]}}}}return ans
}

参考答案PHP

<?php/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param letters int整型二维数组 * @return int整型*/
function maxLetters( $letters )
{usort($letters,function ($a,$b){if($a[0] !=$b[0]){ //长度升序return $a[0]-$b[0];} else{//长度一样，宽度降序return $b[1]-$a[1];}});//长度的最长上升子序列问题$dp = array();$ans =1;for($i=0;$i<count($letters);$i++){$dp[$i] =1;for($j=$i-1;$j>=0;$j--){if($letters[$j][1] < $letters[$i][1]){$cur =$dp[$j]+1;if($dp[$i] < $cur){$dp[$i] =$cur;if($cur>$ans){$ans =$cur;}}}}}return $ans;
}