C++刷LeetCode（面试题 17.08. 马戏团人塔）【sort*】

糖逗

题目描述：

1. 有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。
   
2. 
   
3. 示例：
   
4. 
   
5. 输入：height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110]
   
6. 输出：6
   
7. 解释：从上往下数，叠罗汉最多能叠 6 层：(56,90), (60,95), (65,100), (68,110), (70,150), (75,190)
   
8. 提示：
   
9. 
   
10. height.length == weight.length <= 10000

复制代码

1. bool cmp(pair<int, int> & a, pair<int, int> &b){
   
2.         if(a.first < b.first) return true;
   
3.         else if(a.first == b.first) return (a.second > b.second) ? true : false;
   
4.         else return false;
   
5.     }
   
6. class Solution {
   
7. public:
   
8.     int bestSeqAtIndex(vector<int>& height, vector<int>& weight) {
   
9.         int len = height.size();
   
10.         vector<pair<int, int> > temp(len);
    
11.         for(int i = 0; i < len; i++){
    
12.             temp[i].first = height[i];
    
13.             temp[i].second = weight[i];
    
14.         }
    
15.         sort(temp.begin(), temp.end(), cmp);
    
16.         //for(auto it : temp){
    
17.             //cout << it.first << " " << it.second << endl;
    
18.         //}
    
19.         vector<int> dp;
    
20.         for(int i = 0; i < len ; i++){
    
21.             int id = lower_bound(dp.begin(), dp.end(), temp[i].second) - dp.begin();
    
22.             cout << id << endl;
    
23.             if(id == dp.size()) dp.push_back(temp[i].second);//该数字在dp中没有出现过
    
24.             else dp[id] = temp[i].second;
    
25.         }
    
26.         return dp.size();
    
27.     }
    
28. };

复制代码

注意事项：lower_bound参考链接:https://www.cnblogs.com/Tang-tangt/p/9291018.html