给 n 个信封的长度和宽度。如果信封 a 的长和宽都小于信封 b ,那么信封 a 可以放到信封 b 里,请求出信封最多可以嵌套多少层。
数据范围: ,
要求:空间复杂度 ,时间复杂度
进阶:空间复杂度 ,时间复杂度
进阶:空间复杂度 ,时间复杂度
[[3,4],[2,3],[4,5],[1,3],[2,2],[3,6],[1,2],[3,2],[2,4]]
4
从里到外分别是{1,2},{2,3},{3,4},{4,5}。
[[1,4],[4,1]]
1
时间复杂度O(nlog n),空间复杂度O(n)。
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param letters int二维数组 * @return int */ public int maxLetters (int[][] letters) { // write code here Arrays.sort(letters, (a, b) -> a[0] != b[0]? a[0] - b[0]: b[1] - a[1]); int n = letters.length; int[] ends = new int[n]; // ends[i]表示长度为i+1的递增子序列最小结尾 ends[0] = letters[0][1]; int maxLen = 1, tail = 0; // 最长递增子序列长度与ends数组的有效区末尾下标 for(int i = 1; i < n; i++){ int index = lowerbound(ends, 0, tail, letters[i][1]); ends[index] = letters[i][1]; if(index > tail){ // ends数组的有效区没能找到第一个大于等于letters[i][1]的区域,就扩充ends数组有效区 tail ++; } maxLen = Math.max(maxLen, index + 1); } return maxLen; } private int lowerbound(int[] arr, int L, int R, int target) { int left = L, right = R, idx = R + 1; while(left <= right){ int mid = left + ((right - left) >> 1); if(arr[mid] < target){ left = mid + 1; }else{ idx = mid; right = mid - 1; } } return idx; } }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param letters intvector<vector<>> * @return int */ static bool cmp(vector<int>& a, vector<int>& b) { return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]); } int maxLetters(vector<vector<int> >& letters) { // write code here if(letters.empty()) return 0; int n = letters.size(); // 这一步是将二维转为一维问题 sort(letters.begin(), letters.end(), cmp); // 下面的这个是求解 最长递增子数组 vector<int> f(n, 1); for(int i=1; i<n; i++) { for(int j=0; j<i; j++) { if(letters[j][1] < letters[i][1]) f[i] = max(f[i], f[j] + 1); } } return *max_element(f.begin(), f.end()); } };
package main import "sort" /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param letters int二维数组 * @return int */ func maxLetters( letters [][]int ) int { n:=len(letters) sort.Slice(letters,func(i,j int)bool{ return letters[i][0]<letters[j][0] }) ans:=1 dp:=make([]int,n) for i,lt:=range letters{ dp[i]=1 for j:=0;j<i;j++{ if lt[0]>letters[j][0]&<[1]>letters[j][1]{ dp[i]=max(dp[i],dp[j]+1) } } if ans<dp[i]{ ans=dp[i] } } return ans } func max(a,b int)int{ if a>b{ return a } return b }
class Solution { private: struct letter { int width; int length; bool operator <(const letter& A) { if (width < A.width) return true; if (width > A.width) return false; if (length < A.length) return false; return true; } letter(int w, int l) :width(w), length(l) {} }; public: int maxLetters(vector<vector<int> >& letters) { int size = letters.size(); letter** arr = new letter * [size](); for (int i = 0; i < size; ++i) arr[i] = new letter(letters[i][0], letters[i][1]); sort(arr, arr + size, [](letter* A, letter* B) { return *A < *B; }); int* length = new int[size + 1](); int index = 1; length[1] = arr[0]->length; int temp; for (int i = 1; i < size; ++i) { temp = arr[i]->length; if (temp > length[index]) length[++index] = temp; else if (temp < length[index]) { int left = 1, right = index; int mid; while (1) { mid = left + right >> 1; if (length[mid] > temp) right = mid - 1; else if (length[mid] < temp) left = mid + 1; else break; if (left > right) { length[left] = temp; break; } } } } delete[]length; for (int i = 0; i < size; ++i) delete[]arr[i]; delete[]arr; return index; } };
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param letters int二维数组 * @return int */ public int maxLetters (int[][] letters) { // write code here Arrays.sort(letters, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { if(o1[0]!=o2[0]){ return o1[0]-o2[0]; }else{ return o2[1]-o1[1]; } } }); List<Integer> hs = new ArrayList<>(); for(int i=0;i<letters.length;i++){ int tmp = letters[i][1]; if(hs.isEmpty()||hs.get(hs.size()-1)<tmp){ hs.add(tmp); }else{ int l = 0; int r = hs.size()-1; while(l<=r){ int mid = (l+r)/2; if(hs.get(mid)<tmp){ l = mid+1; }else{ if(mid==0||hs.get(mid-1)<tmp){ hs.set(mid,tmp); break; }else{ r = mid-1; } } } } } return hs.size(); } }
暴力递归
class Solution { public: static bool cmp (const vector<int> a,const vector<int> b) { if(a[0]!=b[0]) return a[0]<b[0]; else return a[1]<b[1]; } int process(vector<vector<int> >& letters, int len,int wide,int times,int index) { if(index==letters.size()) return times; if(len>=letters[index][0] || wide>=letters[index][1]) return process(letters,len,wide,times,index+1); // 要当前的信封 int letterin=process(letters,max(len,letters[index][0]),max(wide,letters[index][1]),times+1,index+1); // 不要当前的信封 int letterout=process(letters,len,wide,times,index+1); return max(letterin,letterout); } int maxLetters(vector<vector<int> >& letters) { // 首先对 lectters 排序 sort(letters.begin(),letters.end(),cmp); int count = process(letters,0,0,0,0); return count; } };
import java.util.*; class Envelope { public int len; public int wid; public Envelope(int weight, int height) { this.len = weight; this.wid = height; } } public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param letters int二维数组 * @return int */ public int maxLetters (int[][] letters) { // write code here if (letters.length == 0 || letters[0].length == 0) return 0; Envelope[] env = getSortedEnvelopes(letters); int[] arr = new int[env.length]; for (int i = 0; i < env.length; i++) { arr[i] = env[i].wid; } return getLongestSeq(arr); } //找arr中最长递增子序列 public int getLongestSeq(int[] arr) { int[] dp = new int[arr.length]; int[] ends = new int[arr.length]; int right = 0; int l = 0; int mid = 0; int r = 0; dp[0] = 1; ends[0] = arr[0]; int max = dp[0]; for (int i = 0; i < arr.length; i++) { l = 0; r = right; while (l <= r) { mid = (l+r) / 2; if (arr[i] > ends[mid]) l = mid + 1; else r = mid - 1; } if (r == right) right++; ends[l] = arr[i]; dp[i] = l+1; max = Math.max(max, dp[i]); } return max; } public class EnvelopeComparator implements Comparator<Envelope> { @Override public int compare(Envelope o1, Envelope o2) { //为了避免长度相同的情况下,宽度小的被宽度大的误认为可以嵌套 //换句话说,按这个排列,但看宽度数组,如是你想宽度比我小,除非你长度比我小 //否则长度若一样,前面的宽度肯定比后面的宽度大 return o1.len != o2.len ? o1.len - o2.len : o2.wid - o1.wid; } } public Envelope[] getSortedEnvelopes (int[][] matrix) { Envelope[] res = new Envelope[matrix.length]; for (int i = 0; i < matrix.length; i++) { res[i] = new Envelope(matrix[i][0], matrix[i][1]); } Arrays.sort(res, new EnvelopeComparator()); return res; } }
class Solution { public: static bool cmp(vector<int>&a,vector<int>&b){ if(a[0]!=b[0]) return a[0]<b[0]; else return a[1]>b[1]; } int maxLetters(vector<vector<int> >& letters) { /* letters的第一列理解为长度 第二列理解为宽度 先按长度升序 当长度相同时宽度降序 便于后边求解LIS */ sort(letters.begin(), letters.end(), cmp); vector<int> b; //存取宽度数据 for (int i = 0; i < letters.size(); i++) { b.push_back(letters[i][1]); } //贪心+二分求解最长递增子序列长度 vector<int> res; //遍历宽度的过程中的贪心LIS res.push_back(b[0]); //第一个宽度总可以无条件放进来 int maxl = 0; //遍历中更新的LIS长度 for(int i = 1; i < b.size(); i++) { if (b[i] > res.back()) { res.push_back(b[i]); }else { int pos = lower_bound(res.begin(), res.end(), b[i]) - res.begin(); //二分 res[pos] = b[i]; } } maxl = res.size(); //最后贪心res长度就是LIS的长度 贪心 总是局部最优嘛 return maxl; } };
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param letters intvector<vector<>> * @return int */ int maxLetters(vector<vector<int> >& letters) { // 使用动态规划,假设dp[i]为第i个信封套在最外面的套娃数目 int N=letters.size(); int *dp=new int[N]; for(int i=0;i<N;i++) dp[i]=1; // 替换次数 int replace=0; do{ replace=0; for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ if(j==i) continue; if(letters[j][0]<letters[i][0] && letters[j][1]<letters[i][1] ){ if( dp[i]<dp[j]+1 ){ dp[i]=dp[j]+1; replace+=1; } } } } } while(replace!=0); int maxdp=0; for(int i=0;i<N;i++){ if(dp[i]>maxdp) maxdp=dp[i]; } return maxdp; } };
class Solution: def maxLetters(self , letters ): # write code here # 其实第一个肯定能套进去。 result = 1 pre = 0 letters = sorted(letters, key = lambda x:(x[0],x[1])) for i in range(1, len(letters)): if letters[i][0] > letters[pre][0] and letters[i][1] > letters[pre][1]: result += 1 pre = i return result
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param letters int二维数组 * @return int */ int res3 = 0; int cur = 0; public int maxLetters (int[][] letters) { // write code here int[] dp = new int[letters.length]; for (int i = 0; i < letters.length; i++) { dfs(letters, dp, i , letters[i][0], letters[i][1], 1, true); dp[i] = cur; } return res3; } public void dfs(int[][] letters, int[] dp, int cur, int length, int width, int size, boolean flag) { for (int i = 0; i < letters.length; i++) { if (letters[i][0] < length && letters[i][1] < width){ if (dp[i] != 0) { size += dp[i]; break; } flag = false; dfs(letters, dp, i, letters[i][0], letters[i][1], size + 1, true); } } if (flag) {res3 = Math.max(res3, size); cur = size;} } }
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param letters int二维数组 # @return int # class Solution: def maxLetters(self , letters ): letters.sort(key=lambda x: (x[0], -x[1])) w, h = 0, 0 cnt = 0 # 转换成最长递增子序列的问题了 def bs(nums, target): # 找到第一个比target大的数,返回index l, r = 0, len(nums)-1 while l < r: m = l + ((r-l)>>1) if nums[m] >= target: r = m else: l = m + 1 return l if nums[l] >= target else l+1 l = [] for i in range(len(letters)): if not l&nbs***bsp;l[-1] < letters[i][1]: l.append(letters[i][1]) else: idx = bs(l, letters[i][1]) l[idx] = letters[i][1] return len(l)
import java.util.*; public class Solution { public int maxLetters (int[][] letters) { // write code here if(letters.length == 0) return 0; Arrays.sort(letters, new Comparator<int[]>(){ public int compare(int[] a, int[] b){ if(a[0] == b[0]) return a[1] - b[1]; else return a[0] - b[0]; } }); int n = letters.length; int[] dp = new int[n]; dp[0] = 1; for(int i = 1; i < n; i++){ for(int j = 0; j < i; j++){ if(letters[i][1] > letters[j][1]) dp[i] = Math.max(dp[i], dp[j]); } dp[i]++; } return dp[n - 1]; } }
动态规划+二分查找
时间复杂度O(nlogn)
空间复杂度O(n)
1.将数组按照从小到大排序;
2.维护两个数组f,g;f[i]表示第i个信封能够嵌套的层数,g[i]表示嵌套层数为i的信封中最后一个信封宽度的最小值;g是单调递增的序列;
3.从前往后遍历数组,保证g数组中信封的长度小于当前信封;利用二分从g数组中查找宽度小于当前数组的最后一个嵌套信封,记其层数为x,当前信封能够嵌套的最大层数就是x+1。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param letters intvector<vector<>> * @return int */ int maxLetters(vector<vector<int> >& w) { // write code here sort(w.begin(), w.end()); int n = w.size(); vector<int> f(n, 0), g(1, 0); int ans = 0; for (int i = 0, j = 0; i < n; i ++) { while (w[j][0] != w[i][0]) { if (g.size() == f[j]) g.push_back(w[j][1]); else g[f[j]] = min(g[f[j]], w[j][1]); j ++; } int l = 0, r = g.size() - 1; while (l < r) { int m = l + r + 1 >> 1; if (w[i][1] > g[m]) l = m; else r = m - 1; } f[i] = r + 1; ans = max(ans, f[i]); } return ans; } };
function maxLetters( letters ) { // write code here let len = letters.length if(!len) return 0 letters.sort((a,b)=> a[0]=== b[0]? a[1]-b[1]:a[0]-b[0]) const dp = new Array(len).fill(1) dp[0] = 1 for(let i = 1;i<len;i++){ for(let j = 0;j<i;j++){ if(letters[i][1]>letters[j][1] && letters[i][0] !== letters[j][0]){ dp[i] = Math.max(dp[i], dp[j]+1) } } } return Math.max(...dp) }