# 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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cai-sen-se.gitbook.io/leetcode/401-600/406.-gen-ju-shen-gao-zhong-jian-dui-lie.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.