题目链接

面试题 17.08. 马戏团人塔 mid

题目描述

有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。

示例：

输入：height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110]
输出：6
解释：从上往下数，叠罗汉最多能叠 6 层：(56,90), (60,95), (65,100), (68,110), (70,150), (75,190)

提示：

• $height.length=weight.length\le 10000$

解法：排序 + 二分 + 贪心

先按 $height$ 升序排序，当身高相同时，再按 $weight$ 降序排序。

比如 $[2,6],[2,5],[2,7],[1,4],[3,8]$ 排序之后就变为 $[1,4],[2,7],[2,6],[2,5],[3,8]$。

接着我们按照第二维，即 $weight$， { 4 , 7 , 6 , 5 , 8 } \{4,7,6,5,8\} {4,7,6,5,8}，求 最长上升子序列 的长度。

最长上升子序列为 { 4 , 5 , 8 } \{ 4,5,8\} {4,5,8}，即 $[1,4],[2,5],[3,8]$，叠罗汉最多叠 $3$ 个人。

最长上升子序列解法

由于 $n=10^4$，我们直接使用动态规划的时间复杂度为 $O(n^2)$，会超时。

会超时的代码：

using PII = pair<int,int>;class Solution {
public:int bestSeqAtIndex(vector<int>& height, vector<int>& weight) {int n = height.size();vector<PII> a;for(int i = 0;i < n;i++){auto h = height[i] , w = weight[i];a.emplace_back(h,w);}sort(a.begin(),a.end(),[&](auto &p,auto &q){if(p.first == q.first) return p.second > q.second;return p.first < q.first;});int ans = 0;vector<int> f(n);for(int i = 0;i < n;i++){f[i] = 1;for(int j = 0;j < i;j++){if(a[i].second > a[j].second) f[i] = max(f[i],f[j] + 1);}ans = max(ans , f[i]);}return ans;}
};

最长子序列，我们可以使用二分来优化，将时间复杂度优化为 $O(n\times logn)$，能够通过本题。

时间复杂度： $O(n\times logn)$

C++代码：

using PII = pair<int,int>;class Solution {
public:int bestSeqAtIndex(vector<int>& height, vector<int>& weight) {int n = height.size();vector<PII> a;for(int i = 0;i < n;i++){auto h = height[i] , w = weight[i];a.emplace_back(h,w);}sort(a.begin(),a.end(),[&](auto &p,auto &q){if(p.first == q.first) return p.second > q.second;return p.first < q.first;});int ans = 0;vector<int> f;for(int i = 0;i < n;i++){if(f.size() == 0 || a[i].second > f.back()) f.push_back(a[i].second);else{auto it = lower_bound(f.begin(),f.end(),a[i].second);*it = a[i].second;}}return f.size();}
};