有个马戏团正在设计叠罗汉的表演节目,一个人要站在另一人的肩膀上。出于实际和美观的考虑,在上面的人要比下面的人矮一点且轻一点。
已知马戏团每个人的身高和体重,请编写代码计算叠罗汉最多能叠几个人。
示例:
输入: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 <= 10000
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/circus-tower-lcci
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
类似题目:
LeetCode 354. 俄罗斯套娃信封问题(最长上升子序 DP/二分查找)
class Solution {
public:
int bestSeqAtIndex(vector<int>& height, vector<int>& weight) {
int i, j, n = height.size(),maxP = 1;
vector<vector<int>> p(n);
for(i = 0; i < n; ++i)
p[i] = {height[i], weight[i]};
sort(p.begin(),p.end());//按身高升序
vector<int> dp(n,1);
for(i = 1; i < n; ++i)
{
for(j = i-1; j >= 0; --j)
{
if(p[i][1] > p[j][1])
{
dp[i] = max(dp[i], 1+dp[j]);
maxP = max(maxP, dp[i]);
}
}
}
sort(p.begin(),p.end(),[&](auto a, auto b){
return a[1] < b[1];
});//按体重升序
vector<int> dp1(n,1);
for(i = 1; i < n; ++i)
{
for(j = i-1; j >= 0; --j)
{
if(p[i][0] > p[j][0])
{
dp1[i] = max(dp1[i], 1+dp1[j]);
maxP = max(maxP, dp1[i]);
}
}
}
return maxP;
}
};
dp[i]
表示长度为 i
的上升子序的 序列最后一个数的最小值
(采用二分查找,找到第一个大于等于 target 的)class Solution {
public:
int bestSeqAtIndex(vector<int>& height, vector<int>& weight) {
int i, idx=0, n = height.size();
vector<pair<int,int>> p(n);
for(i = 0; i < n; ++i)
p[i] = {height[i], weight[i]};
sort(p.begin(),p.end(),[](auto a, auto b){
if(a.first==b.first)
return a.second > b.second;
//升高一样,降序,避免选择上升子序时把他们同时选上
return a.first < b.first;
});//按身高升序
vector<int> dp(n);
for(i = 0; i < n; ++i)
{
auto it = lower_bound(dp.begin(),dp.begin()+idx,p[i].second);
//二分查找求体重的最长上升子序
*it = p[i].second;
if(it-dp.begin()==idx)
idx++;
}
return idx;
}
};
404 ms 46.3 MB
class Solution {
public:
int bestSeqAtIndex(vector<int>& height, vector<int>& weight) {
int i, j, len=1, n = height.size();
vector<pair<int,int>> p(n);
for(i = 0; i < n; ++i)
p[i] = {height[i], weight[i]};
sort(p.begin(),p.end(),[](auto a, auto b){
if(a.first==b.first)
return a.second > b.second;
//升高一样,降序,避免选择上升子序时把他们同时选上
return a.first < b.first;
});//按身高升序
vector<int> dp(n);
dp[0] = p[0].second;
for(i = 1; i < n; ++i)
{
j = bs(dp,0,len-1,len,p[i].second);//二分查找求体重的最长上升子序
dp[j] = p[i].second;
if(j == len)
len++;
}
return len;
}
int bs(vector<int>& dp, int l, int r, int len, int target)
{ //第一个 大于等于 我的
int mid;
while(l <= r)
{
mid = l+((r-l)>>1);
if(dp[mid] >= target)
{
if(mid==0 || dp[mid-1] < target)
return mid;
else
r = mid-1;
}
else// if(dp[mid] < target)
l = mid+1;
}
return len;//没有找打,说明它是最大的
}
};
264 ms 46.5 MB