根据身高重建队列:贪心算法

字数: 1031

经典的贪心算法题，带有两个维度，需要权衡两个维度。

题目

力扣：406. 根据身高重建队列
一群乱序的人站成一个队列，称为数组 people。
有: $people[i] =[h_i, k_i]$ 表示第 $i$ 个人的身高为 $h_i$，前面正好有 $k_i$ 个身高大于或等于 $h_i$ 的人。
返回排序好的队列，其中 $queue[j] = [h_j, k_j]$ 是队列中第 $j$ 个人的属性。

1
2
3
4
5
6

class Solution {
  public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        
    }
};

题解

这道题有两个维度：h、j。主要是要确保每个人前面正好有 $k$ 个身高大于或等于他自己的人。
要确定排序逻辑，可以知道高个子插入队列后后续插入的矮个子不会影响高个子的 $k$ 值，假若当身高相同时，应该让 k 值小的排前面，这样正好符合题目对 k 的要求。
此为：先固定一个约束，再处理另一个约束。
所以正确的排序规则应该是：按身高从高到低排序，身高相同则按 k 从小到大排序。
因此可以写出排序函数，通过静态函数后续以函数指针的形式在 sort 中调用是可行的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

/*
 * 比较函数
 * 按 h 降序，k 升序
 */
static bool cmp(const std::vector<int> &x, const std::vector<int> &y)
{
    if (x[0] != y[0])
        return x[0] > y[0];
    return x[1] < y[1];
}

此时按排序好的顺序，对每个元素按 k 的索引顺序进行插入到对于队列位置即可。
比如第一个元素的 k 肯定是 0。

1

std::vector<std::vector<int>> people = {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};

比如这个数据，{5, 2} 排序前是：

1

{{5, 0}, {7, 0}, {6, 1}, {4, 4}, {7, 1}}

这时将 {5, 2} 插入索引为 2 的位置上可行的，因为前面两个数的身高都大于等于 5。

这样的解题思路是局部最优推出全局最优，符合弹性算法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

static bool cmp(const std::vector<int> &x, const std::vector<int> &y)
{
    if (x[0] != y[0])
        return x[0] > y[0];
    return x[1] < y[1];
}
std::vector<std::vector<int>> reconstructQueue(std::vector<std::vector<int>> &people)
{
    int i;
    std::vector<std::vector<int>> queue;
    /*
     * 对数组排序，排序规则是身高降序，k 值升序
     * x 代表列表中的每个元素
     * x[1] 表示在身高相同的情况下，对 k 值升序排序
     * x[0] 表示对身高降序排序
     */
    std::sort(people.begin(), people.end(), cmp);

    // 遍历排好序的每一个人，把它插入到队列中索引为 k 的位置
    for (i = 0; i < people.size(); i++)
        queue.insert(queue.begin() + people[i][1], people[i]);
    return queue;
}

有一些 c++ 语法细节的地方：

  • vector 的 insert 方法的第一个参数 pos 传入的是迭代器，而不能是索引位置，索引位置只好通过 begin() + 索引来得到。
  • 在类里面调用类方法的函数指针要把被调函数添加上 static 成为静态成员函数才能调用。

python 解法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def reconstructQueue(people: list[list[int]]) -> list[list[int]]:
    # 对数组排序，排序规则是身高降序，k 值升序
    # x 代表列表中的每个元素
    # x[0] 表示对身高降序排序
    # x[1] 表示在身高相同的情况下，对 k 值升序排序
    people.sort(key=lambda x: (-x[0], x[1]))
    queue = []
    # 遍历排好序的每一个人，把它插入到队列中索引为 k 的位置
    for p in people:
        queue.insert(p[1], p)
    return queue

排序的 lambda 挺优美，-x[0] 即对 h 降序，x[1] 即对 k 升序

参考资料

  1. bilibili 根据身高重建队列 | 编程面试必刷题
  2. 知乎 「leetcode」406.根据身高重建队列【贪心算法】详细图解