LeetCode 面试题 17.08 —— 马戏团人塔

本文主要是介绍LeetCode 面试题 17.08 —— 马戏团人塔，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

阅读目录

- 1. 题目
- 2. 解题思路
- 3. 代码实现

1. 题目

2. 解题思路

首先，我们对人的身高按照从小到大排序，特别注意，对于身高相等的人，要按照体重从高到低排序。这时候，序列已经满足了在上面的人要比下面的人矮一点，然后，我们只需要保证提取到一个最长的体重的上升子序列即可。这一步骤也就是 LeetCode 300——最长上升子序列的解答思路，贪心+二分查找。

为什么身高相等的情况下，要按照体重从高到低排序呢？因为，如果按照体重从低到高排序的话，第二个步骤身高相等的人就会满足体重的上升子序列，但实际上，题目要求的则是上面的人要比下面的人高一点，所以身高相同的情况下只能保留一个体重最小的。

比如身高是 $[2, 3, 3, 3, 5, 8]$ ，体重是 $[3, 5, 5, 4, 2, 6]$ ，最终满足要求的其中一个序列是 $[(2, 3), (3, 4), (8, 6)]$ 。

而如果体重按照升序排列的话，那么身高是 $[2, 3, 3, 3, 5, 8]$ ，体重是 $[3, 4, 4, 5, 2, 6]$ ，得到的答案则是 $[(2, 3), (3, 4), (3, 5), (8, 6)]$ ，这是不满足题意要求的。

3. 代码实现

class Solution {
public:void quickSort(vector<int>& height, vector<int>& weight, int left, int right) {if (left < right) {int pivot = height[right];int i = left;for (int j = left; j <= right; ++j) {// 身高从小到大排，身高相等时，体重从大到小if (height[j] < pivot || (height[j] == pivot && weight[j] >= weight[right]) ) {int temp = height[i];height[i] = height[j];height[j] = temp;temp = weight[i];weight[i++] = weight[j];weight[j] = temp;}}quickSort(height, weight, left, i-2);quickSort(height, weight, i, right);}}int bestSeqAtIndex(vector<int>& height, vector<int>& weight) {if (height.empty()) {return 0;}quickSort(height, weight, 0, height.size()-1);vector<int> new_weight = {weight[0]};for (int i = 1; i < weight.size(); ++i) {if (weight[i] > new_weight.back()) {new_weight.push_back(weight[i]);} else if (weight[i] < new_weight.back()) {int l = 0;int r = new_weight.size()-1;int pos = -1;while (l <= r) {int mid = l + (r - l) / 2;if (new_weight[mid] == weight[i]) {break;// 找到第一个比weight[i]大的位置进行替换} else if (new_weight[mid] > weight[i]) {if (mid == 0 || new_weight[mid-1] < weight[i]) {pos = mid;break;} else {r = mid - 1;}} else {l = mid + 1;}}if (pos != -1) {new_weight[pos] = weight[i];}}}return new_weight.size();}
};