LeetCode 406 根据身高重建队列

https://leetcode-cn.com/problems/queue-reconstruction-by-height/

贪心

这是一道贪心的题目，然而我是看了力扣题解才明白它的贪心策略的。??

因为对一个整数对(h, k)要求它前面必须有k个人的身高不低于h。所以，我们不妨按照身高从低到高依次重建。对于队列中剩余人群中身高最矮的人来说，因为队列中除他之外的人的身高都大于等于他，所以他的k值就指明了它前面的空位（所有空位中的人的身高都是大于等于他的，只不过还没轮到他们，所以还空着）必须有k个，所以他必须排在重建后队列的第k+1个空位上。把他排序之后，然后再排序第二矮的人，直到把所有的人都排序完毕即可。

比如，输入是[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]，身高最矮的是h = 4，且只有一个，根据其k=4，将他放到第5个位置上。如下图1所示。

如果有两个人的身高h一样但k不一样，此时应该先安排谁呢？ 还是上面的例子，我们发现身高h为5的人有两个，它们的k值分别为0和2。如图2所示，假如我们先安排(5, 0)，那么在安排(5, 2)时，根据队列中空着的位置的人的身高都是大等于他的这个判断原则，由于(5, 0)已经占据了位置1，位置1不空，那么算法会错误得将(5, 2)安排到队列中第4个位置处。所以我们不能先安排k小的，而应该优先安排k值大的。

当有多人身高h一样时，我们就需要按照k值从大到小的顺序安排。如下图3所示，先安排(5, 2)再安排(5, 0)，算法能够正确地将两人的位置安排正确。

终于啰嗦清楚了，算法思路：
（1）先对输入队列排序，按照身高h从小到大，k值从大到小的顺序排序
（2）对于排序后的队列中的元素(h, k)，将其放在第k+1个空位处（注意是空位），直到整个输入队列重建完成

代码如下：

// 排序规则
struct MyCompare {
    bool operator()(const vector<int>& a, const vector<int>& b) {
        if (a[0] != b[0]) return a[0] < b[0];
        else return a[1] > b[1];
    }
} cmp;

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);

        int k;
        int sz = people.size();
        vector<vector<int>> ans(sz, vector<int>(2, -1));    // 全部初始化为-1以示区别

        for (int i = 0; i < sz; ++i) {
            k = people[i][1];
            int j = 0;
            // 从新队列第一位起往前数k个空位
            for (j = 0; j < sz && k > 0; ++j) {
                if (ans[j][0] == -1) --k;
            }
            // 找到第k+1个空位然后将people[i]存入新队列中
            for (; j < sz; ++j) {
                if (ans[j][0] == -1) {
                    ans[j][0] = people[i][0];
                    ans[j][1] = people[i][1];
                    break;
                }
            }
        }

        return ans;
    }
};

LeetCode 406 根据身高重建队列

原文：https://www.cnblogs.com/wallace-lai/p/13985425.html