406根据身高重建队列 406根据身高重建队列

题目描述
假设有打乱顺序的一群人站成一个队列。每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。编写一个算法来重建这个队列。
输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
问题分析

先排身高更高的，这是要防止后排入人员影响先排入人员位置
每次排入新人员[h,k]时，已处于队列的人身高都>=h，所以新排入位置就是people[k]

【406根据身高重建队列】先将people按照身高降序排序，又由于每次插入的位置是k，所以相同身高需要按k升序排序，否则插入位置会越界
由于后续需要频繁使用insert()操作，建议使用list作为中间容器
循环地从头读取people，根据people[i][1]也就是k,插入list，注意list的迭代器不支持随机访问，需要使用advance()找到应插入位置
将完成所有插入操作的list重建为vector返回
https://leetcode-cn.com/problems/queue-reconstruction-by-height/solution/406-gen-ju-shen-gao-zhong-jian-dui-lie-8xing-dai-m/
解题思路1

class Solution { public:vector> reconstructQueue(vector>& people) { //排序 sort(people.begin(), people.end(), [](const vector&lhs, const vector& rhs) {return lhs[0] == rhs[0] ? lhs[1] <= rhs[1] : lhs[0] > rhs[0]; }); int len = people.size(); list> tmp; //循环插入 for (int i = 0; i < len; ++i) { auto pos = tmp.begin(); //pos迭代器向前people[i][1]个位置 advance(pos, people[i][1]); tmp.insert(pos, people[i]); } //重建vector返回 return vector>(tmp.begin(), tmp.end()); } };