跳到主要内容

LeetCode 406. 根据身高重建队列

本节目标

先固定身高更高的人，再按 k 值插入，逐步保持已构造前缀有效。

这是局部约束与构造中的插入构造拓展题。

题意与约束​

每人以 [h,k] 表示：其前方恰有 k 个身高不低于 h 的人。重建任意一个满足所有描述的队列。

直接思路与瓶颈​

从矮到高安排时，未来插入的高个子会改变已有人的 k 计数。直接寻找每个人的位置会不断推翻之前的选择。

贪心模型与算法推导​

按身高降序、k 升序排序。此时已放入队列的人都不矮于当前人，把当前人插入下标 k，前方恰好有 k 个对其有效的高个或等高者。

正确性依据​

按身高降序、同身高按 k 升序处理。处理当前人时，队列中所有人都不矮于当前人，故插入下标 k 后，前方恰有 k 人会被它计数。之后插入的更矮者不计入已有高个子的约束；之后插入的同身高者 k 更大，且会排在已处理同身高者之后。因此每个已插入元素前方“身高不低于它”的人数始终保持正确。

样例执行过程​

排序后为 [7,0],[7,1],[6,1],[5,0],[5,2],[4,4]。依次按 k 插入，队列演化为 [7,0]、[7,0],[7,1]、[7,0],[6,1],[7,1]，最终得到 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]。

代码实现​

C++17
#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>> people) {
        sort(people.begin(), people.end(), [](const vector<int>& first, const vector<int>& second) {
            return first[0] != second[0] ? first[0] > second[0] : first[1] < second[1];
        });
        vector<vector<int>> queue;
        for (const auto& person : people) queue.insert(queue.begin() + person[1], person);
        return queue;
    }
};

复杂度分析​

排序为 O(n log n)，数组中间插入累计 O(n²)；结果队列占用 O(n) 空间。

边界与易错点​

  • 相同身高必须按 k 升序。
  • 不能先安排矮个子。
  • 题目保证输入存在可行解，插入下标因此合法。

模式迁移​

若后续操作不会影响已处理元素的约束计数，应先处理“影响力更强”的元素，再用位置插入构造答案。