> For the complete documentation index, see [llms.txt](https://cai-sen-se.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cai-sen-se.gitbook.io/leetcode/401-600/406.-gen-ju-shen-gao-zhong-jian-dui-lie.md).

# 406. 根据身高重建队列

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

## 解法一：

先将vector排序,按h排序(降序),h值相等按k值排(升序)

```
7 0
7 1
6 1
5 0
5 2
4 4
```

第一次:**\[7,0]**&#x20;

第二次:\[7,0],**\[7,1]**&#x20;

第三次:\[7,0],**\[6,1]**,\[7,1]&#x20;

第四次:**\[5,0]**,\[7,0],\[6,1],\[7,1]&#x20;

第五次:\[5,0],\[7,0],**\[5,2],**\[6,1],\[7,1]&#x20;

第六次:\[5,0],\[7,0],\[5,2],\[6,1],**\[4,4]**,\[7,1]

算法的简单解释就是:排序处理后,h值大的放前面,因为越大的数限制越小;而越小的数由于要保证前面有k个比他大的数,**限制越多**. \
对于h值相等的数,就看k值,**因为小的数不会影响大数的k**,所以先放大数之后,小数就可以直接放到vector的第k个位置,而不会影响别人.\
这里用到sort的三参数版本,最后一个参数为比较函数 \
<http://zh.cppreference.com/w/cpp/algorithm/sort>

```
template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

first, last - 要排序的元素范围

comp - 比较函数对象（即满足比较 (Compare) 概念的对象），若第一参数小于（即先序于）第二参数则返回 ​true 。
比较函数的签名应等价于如下者：

 bool cmp(const Type1 &a, const Type2 &b);

签名不必拥有 const & ，但函数对象必须不修改传递给它的对象。
类型 Type1 与 Type2 必须使得 RandomIt 类型的对象能在解引用后隐式转换到这两个类型。 ​
```

c++:

```cpp
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
    //先对people做排序处理,其中比较函数使用lambda表达式
    sort(people.begin(), people.end(), [](const pair<int, int> p1, const pair<int, int> p2)
        { return p1.first > p2.first || (p1.first == p2.first && p1.second < p2.second); });
    vector<pair<int, int>> res;
    for (auto p : people) {  //从头遍历people,将p按k值插入res
        res.insert(res.begin()+p.second, p);
    }
    return res;
}
```

py：重点在于lambda表达式的骚操作

```python
class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        #用sort排序，lambda表达式表示按第一个元素降序，第一个相等则按第二个升序
        people = sorted(people, key=lambda x:(-x[0], x[1]))
        res = []
        for i in range(len(people)):
            k = people[i][1]  #取people成员的k值
            res.insert(k, people[i])  #按k值插入
        return res
```