> For the complete documentation index, see [llms.txt](https://851958789.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://851958789.gitbook.io/notes/0406_queue_reconstruction_by_height/slt.md).

# Solution1 greedy

* 时间复杂度 $O(n^2)$

    要在中间 insert
* 空间复杂度 $O(n)$

先对输入数组排序，h降序，k升序

// Input: // \[\[7,0], \[4,4], \[7,1], \[5,0], \[6,1], \[5,2]]

// Output: // \[\[5,0], \[7,0], \[5,2], \[6,1], \[4,4], \[7,1]]

h降序，k升序排好序 \[7,0], \[7,1], \[6,1], \[5,0], \[5,2], \[4,4]

然后按照 k 为索引 insert。

矮的在后面，后插入。所以插入完之后k相等h小的在前面

res = \[\[7,0]] res = \[\[7,0], \[7,1]] res = \[\[7,0], \[6,1], \[7,1]] res = \[\[5,0], \[7,0], \[6,1], \[7,1]] res = \[\[5,0], \[7,0], \[5,2], \[6,1], \[7,1]] res = \[\[5,0], \[7,0], \[5,2], \[6,1], \[4,4], \[7,1]]

身高从高到低排序的好处是，对于前面已经排好的队， 1.如果下一个人(h,k)比前面所有人都矮，那么，他插入队列的k处，使其达到k的要求，对其他人没影响，达到要求！ 2.如果下一个人跟之前排好队的人中最矮的身高一样，这时候，就体现为什么之前排序时候，先考虑身高，再按照k的升序了，这时候，新来的人虽然与之前最矮之人身高一样，但是由于他的k比之前最矮的人的k都大，所以，他插入的地方一定在已经排好队的，和他身高一样的，最矮之人的后面，对这些最矮人们没有影响，当然，对其他比他高的人就更没有影响了。

其只要了解一点：我们一个一个地排队，对于前面已经排好的队，如果我们在k的位置插入一个新人，那么对k之前的人没有任何影响，对于k之后比新人高的人也没有任何影响，因此，我们每插入一个人的时候，要么保证前面所有人都比新人高，要么至少保证插入的位置后面的所有人都比新人高。