[数据结构与算法]1020-根据身高重建队列

题目如下

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

解题思路

方法一：从低到高考虑

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>> ans(n);
        for (const vector<int>& person : people)
        {
            int spaces = person[1] + 1;
            for (int i = 0; i < n; ++i) 
            {
                if (ans[i].empty()) 
                {
                    --spaces;
                    if (!spaces) 
                    {
                        ans[i] = person;
                        break;
                    }
                }
            }
        }
        return ans;
    }
};

方法二：从高到低考虑

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]);
            });
        vector<vector<int>> ans;
        for (const vector<int>& person : people) 
        {
            ans.insert(ans.begin() + person[1], person);
        }
        return ans;
    }
};