[[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)。
动态规划+二分查找
时间复杂度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) }