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

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();

    }
};