|
給你一個(gè)二維整數(shù)數(shù)組 envelopes ，其中 envelopes[i] = [wi, hi] ,，表示第 i 個(gè)信封的寬度和高度,。 當(dāng)另一個(gè)信封的寬度和高度都比這個(gè)信封大的時(shí)候，這個(gè)信封就可以放進(jìn)另一個(gè)信封里,，如同俄羅斯套娃一樣,。 請(qǐng)計(jì)算 最多能有多少個(gè) 信封能組成一組“俄羅斯套娃”信封（即可以把一個(gè)信封放到另一個(gè)信封里面）。 注意：不允許旋轉(zhuǎn)信封,。 輸入：envelopes = [[5,4],[6,4],[6,7],[2,3]] 輸入：envelopes = [[1,1],[1,1],[1,1]] 本題和面試題 17.08. 馬戲團(tuán)人塔一樣是最長遞增子序列的二維模式 我們可以對(duì)第一維進(jìn)度升序的排序，然后對(duì)第一維相等的數(shù)進(jìn)行降序的排序,，這樣就可以不管第一維,，直接進(jìn)行第二維的最長遞增子序列求解。 先看個(gè)例子,，假如排序的結(jié)果是下面這樣：
主要有底下兩種解法,，一種是動(dòng)態(tài)規(guī)劃,，還一種是貪心+二分 class Solution { public: // 動(dòng)態(tài)規(guī)劃 int bestSeqAtIndex(vector<int>& height, vector<int>& weight) { int num = height.size(); vector<vector<int>> temp(num); vector<int> dp(num,1); int maxnum = 1; for(int i = 0; i < num; i++){ temp[i] = {height[i],weight[i]}; } sort(temp.begin(),temp.end(),[](vector<int> &temp1, vector<int> &temp2){ return temp1[0] < temp2[0] || temp1[0] == temp2[0] && temp1[1] > temp2[1]; }); for(int i = 0; i < num; i++){ for(int j = 0; j < i; j++){ if(temp[j][1] < temp[i][1]){ dp[i] = max(dp[i],dp[j] + 1); maxnum = max(maxnum,dp[i]); } } } return maxnum; } };
class Solution { public: /* 先按寬從小到大排序，但是同一個(gè)寬度的按高度從大到小排序,，然后高度就按最長子序列這種題型來做(貪心 + 二分),。 */ int maxEnvelopes(vector<vector<int>>& envelopes) { sort(envelopes.begin(),envelopes.end(),[](vector<int> &x1, vector<int> &x2){ return x1[0] < x2[0] || (x1[0] == x2[0] && x1[1] > x2[1]); }); int length = envelopes.size(); vector<int> tail; int maxnum = 1; tail.push_back(envelopes[0][1]); for(int i = 0; i < length; i++){ if(envelopes[i][1] > tail.back()){ tail.push_back(envelopes[i][1]); } else{ vector<int> ::iterator iter = lower_bound(tail.begin(),tail.end(),envelopes[i][1]); *iter = envelopes[i][1]; } } return tail.size(); } };
|
|
|
