[数据结构与算法]LeetCode 406. 根据身高重建队列

406. 根据身高重建队列

贪心算法

解题思路

按身高从大到小排序，让高个子站在前面。那么对于排序完的数组，每次插入的节点都比前面的节点小，自然不会影响前面的节点的k值。

考虑一种特殊情况：身高相同

这种情况下要按k值从小到大排序，因为如果不这样，例如 $[5,2],[5,0]$，这种情况下 $[5,0]$ 的插入会影响 $[5,2]$ 的k值

代码实现

class Solution
{
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>> &people)
    {
        sort(people.begin(), people.end(), [](const vector<int> &u, const vector<int> &v)
             { return u[0] > v[0] || (u[0] == v[0] && u[1] < v[1]); });
        int n = people.size();
        vector<vector<int>> res;
        for (auto i : people)
        {
            res.insert(res.begin() + i[1], i);
        }
        return res;
    }
};