0406. Queue Reconstruction by Height ==================================== 题目信息 -------- :题号: 0406 :难度: Medium :主题: 队列约束、身高、前方人数、合法重排 :原题: `LeetCode 0406 `_ :重点: ``k`` 只统计前方身高不低于本人者、每个人恰好使用一次、返回任意满足全部约束的队列 题目重述 -------- 数组 ``people`` 中每个人由 ``[h, k]`` 表示:``h`` 是此人的身高,``k`` 是最终队列中排在此人前面且身高大于或等于 ``h`` 的人数。 重新排列所有人,使每个 ``[h, k]`` 的约束同时成立,并返回任意一个合法队列。输入中的每个人必须在结果中恰好出现一次。``people.length`` 位于 ``[1, 2000]``,``h`` 位于 ``[0, 10^6]``,``k`` 位于 ``[0, people.length-1]``;题目保证至少存在一个合法重排。 自建示例 -------- 相同身高也会计入前方人数: .. code-block:: text 输入:people = [[4, 2], [6, 0], [4, 1], [5, 0]] 输出:[[5, 0], [4, 1], [4, 2], [6, 0]] 解释:第一个身高 4 的人前面有一个身高不低于 4 的人;第二个身高 4 的人前面有两人满足条件。身高 6 的人前面没有身高不低于 6 的人。 单个人: .. code-block:: text 输入:people = [[3, 0]] 输出:[[3, 0]] 解释:唯一的人前面没有其他人,其约束自然成立。 先放高个子,再用 k 决定位置 ---------------------------- 按身高降序排列,身高相同按 ``k`` 升序排列。处理当前人时,所有已经放入队列的人身高都不低于当前人,因此把他插入下标 ``k`` 的位置后,前面恰好有 ``k`` 个满足条件的人。身高相同者按 ``k`` 升序处理,插入位置也不会破坏已经满足的同高约束。 较矮的人尚未放入时不会被当前人的 ``k`` 计数;等处理到他们时,当前高个子已经固定,插入到指定位置只会影响较矮者的前方数量。 C++ 实现 -------- .. code-block:: cpp class Solution { public: std::vector> reconstructQueue( std::vector>& people) { std::sort(people.begin(), people.end(), [](const std::vector& first, const std::vector& second) { if (first[0] != second[0]) { return first[0] > second[0]; } return first[1] < second[1]; }); std::vector> queue; for (const auto& person : people) { queue.insert(queue.begin() + person[1], person); } return queue; } }; 代码分析 -------- 插入时队列前方只有已处理的高个子或同高者,故下标 ``k`` 与题目计数完全对应;后续更矮的人不会改变当前人的计数。排序为 ``O(n log n)``,每次向量插入最坏移动 ``O(n)`` 个元素,总时间 ``O(n^2)``,额外空间为 ``O(n)``。