在刷力扣的过程中，遇到有两个维度需要同时考虑的题目时，我们往往会陷入“顾此失彼”的窘境。LeetCode第406题「根据身高重建队列」就是这样一道经典的双维度贪心题。

核心思路解析

题目给定的数组中，每个元素包含两个值：[h, k]，其中 h 代表身高，k 代表前面身高大于或等于 h 的人数。

遇到这种两个维度（h 和 k）相互影响的题目，切忌同时考虑两个维度，一定会乱！

正确的做法是：先按照一个维度进行排序，确定下来后，再处理另一个维度。

第一步：排序（确定维度 h）

如果我们按照身高 h 从大到小排序（如果 h 相同，则按照 k 从小到大排序），排完序之后我们会发现一个绝妙的性质：在任何一个元素的前面，所有人的身高都大于或等于它！

第二步：插入（确定维度 k）

因为排完序后，前面的元素一定比后面的高（或一样高）。所以当我们遍历数组，把当前元素插入到索引为 k 的位置时，它后面的较矮的元素无论怎么移动，都不会影响当前元素的 k 值！

总结成一句话：高个子先站好位，矮个子再插队，矮个子的操作不会影响高个子的相对满足条件。

---

三语代码实现

1. Python版本

Python由于内置了极其方便的排序按键（key），甚至不需要单独写 cmp 函数，利用 lambda 表达式即可优雅解决。

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        que = []
        people.sort(key = lambda x : (-x[0], x[1]))

        for p in people:
            que.insert(p[1], p)

        return que

2. C++版本

C++得益于STL强大的 vector 和 insert API，代码会简洁很多。由于 vector 的底层也是连续内存，insert 操作会自动帮我们完成元素后移的工作（时间复杂度为 O(N)）。

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    // C++中的排序函数写法，返回true表示a排在b前面
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        if (a[0] == b[0]) return a[1] < b[1]; // 身高相等，k小的在前
        return a[0] > b[0];                   // 身高不等，高的在前
    }

    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        // 1. 排序
        sort(people.begin(), people.end(), cmp);
        
        vector<vector<int>> que;
        // 2. 插入
        for (int i = 0; i < people.size(); i++) {
            int position = people[i][1]; // 获取k值作为插入索引
            que.insert(que.begin() + position, people[i]);
        }
        return que;
    }
};

3. C语言版本

#include <stdio.h>
#include <stdlib.h>

// 自定义排序规则
int cmp(const void *p1, const void *p2) {
    int *pp1 = *(int**)p1;
    int *pp2 = *(int**)p2;
    // 若身高相同，则按照k从小到大排列
    // 若身高不同，按身高从大到小排列
    return pp1[0] == pp2[0] ? pp1[1] - pp2[1] : pp2[0] - pp1[0];
}

// 将start与end中间的元素都后移一位
// start为将要新插入元素的位置
void moveBack(int **people, int peopleSize, int start, int end) {
    int i;
    for(i = end; i > start; i--) {
        people[i] = people[i-1];
    }
}

int** reconstructQueue(int** people, int peopleSize, int* peopleColSize, int* returnSize, int** returnColumnSizes){
    int i;
    // 1. 将people按身高从大到小排列（若身高相同，按k从小到大排列）
    qsort(people, peopleSize, sizeof(int*), cmp);

    // 2. 遍历并执行插入操作
    for(i = 0; i < peopleSize; ++i) {
        // people[i]要插入的位置即为它的 k 值
        int position = people[i][1];
        int *temp = people[i];
        
        // 将position到i中间的元素后移一位
        moveBack(people, peopleSize, position, i);
        // 将temp放置到真正的position处
        people[position] = temp;
    }
    
    // 3. 设置返回参数
    *returnSize = peopleSize;
    *returnColumnSizes = (int*)malloc(sizeof(int) * peopleSize);
    for(i = 0; i < peopleSize; ++i) {
        (*returnColumnSizes)[i] = 2;
    }
    return people;
}

疑问：这cmp函数是咋回事？

1. people 的类型是 int**

题目给的 people 是一个二维数组，但 C 里用 int** 表示：
people 指向一个指针数组，数组里每个元素都是 int*，每个 int* 又指向一个长度为 2 的一维数组 [身高, k]。

也就是说：

people[i] 的类型是 int*   (指向一个包含2个int的数组)

2. qsort 如何传递元素

qsort(people, peopleSize, sizeof(int*), cmp);

• 待排序的数组是 people，它的每个元素大小是 sizeof(int*)（即一个指针的大小）。

• 比较函数 cmp 收到的 p1、p2，是指向这两个待比较元素的指针。

关键就在这里：
待比较的元素本身已经是一个指针（int*）了，那么指向这个元素的指针，就是指向指针的指针，即 int**。

所以：

• p1 的类型是 const void *，但它实际指向的是 people 数组中的某个 int* 元素。

• 因此 p1 的真实类型是 int**（指向 int* 的指针）。

3. 正确的转换过程

int *pp1 = *(int**)p1;

分两步看：

1. (int**)p1
   把 void* 强制转换成 int**，告诉编译器“这是一个指向 int* 的指针”。

2. *(int**)p1
   解引用这个 int**，得到它指向的那个 int*。
   这个 int* 正是原始数组里保存的指针，指向某个人的 [身高, k] 数据。

最后把得到的 int* 赋给 pp1，pp1 现在就指向那个长度为 2 的一维数组。

于是就可以用：

pp1[0]  // 身高
pp1[1]  // k

为什么不能直接 (int*)p1？

如果你写 int *pp1 = (int*)p1;，那 pp1 拿到的就是 p1 这个地址本身（把地址值当整数再转成指针），而不是数组里存储的那个指针。这样根本访问不到正确的人的数据。

总结成一句话：
qsort 传进来的是“元素的地址”，而这里的元素本身已经是一个指针，所以需要先强转成 int** 再解引用，才能拿到原始的那个 int*，进而访问 [身高, k]。

总结

贪心算法往往没有固定的套路，但这道题给出了一个非常典型的范例：遇到多维度问题，务必分解动作，化繁为简。 先搞定身高，再搞定站位，局部最优最终推导出了全局最优。

照例贴上卡哥的代码随想录

406.根据身高重建队列 | 贪心 | 排序 | 插入 | 代码随想录-全网最全算法数据结构刷题学习路线|图文+视频教程|免费开源