LeetCode/solutions/406. Queue Reconstruction by Height.md

# [406. Queue Reconstruction by Height](https://leetcode.com/problems/queue-reconstruction-by-height/)

# 思路

有这样一个队列，队列中的每个元素是一个pair，分别为一个人的身高和前面身高不低于当前身高的人的个数，现在这个队列被随机打乱了，让我们恢复这个队列。

## 思路一

假设我们现在已有了一个满足题意的队列`q`，然后新来了一个人`p`且这个人的身高小于（或等于）该队列中的所有身高，那我们应该怎样将新来的这个人插入到原队列呢？很简单，应该将这个人插入到位置`p[1]`处，即`q.insert(q.begin()+p[1], p)`;

所以我们可以从一个空队列开始不断插入所有人，为了满足上面的条件“这个人的身高小于（或等于）该队列中的所有身高”，我们应该先对所有人进行排序，身高高的排前面，身高一样的话，则第二个数小的排前面。然后新建一个空的数组，遍历之前排好序的数组，然后根据每个元素的第二个数字，将其插入到 res 数组中对应的位置。

由于数组的插入是O(n)的，所以总的时间复杂度为O(n^2)

## 思路二

思路一开辟了外的数组，其实我们可以在元素组上进行插入。还是先排序，然后从前往后遍历，将当前元素插入到前面的合适位置。这里的插入需要我们手动将需要移动的元素往后移一步。

复杂度同思路一，但是实际测试要快不少。


# C++
## 思路一
``` C++
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), [](const vector<int>&a, const vector<int>&b){
            return a[0] != b[0] ? a[0] > b[0] : a[1] < b[1];
        });
        vector<vector<int>>res;
        for(auto p: people)
            res.insert(res.begin() + p[1], p);
        
        return res;
    }
};
```


## 思路二
``` C++
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), [](const vector<int>&a, const vector<int>&b){
            return a[0] != b[0] ? a[0] > b[0] : a[1] < b[1];
        });
        
        int h, k;
        for(int i = 1; i < people.size(); i++){
            h = people[i][0]; k = people[i][1];
            for(int j = i; j > k; j--){
                people[j][0] = people[j-1][0];
                people[j][1] = people[j-1][1];
            }
            people[k][0] = h; people[k][1] = k;
        }
        
        return people;
    }
};
```