LC406 根据身高重建队列

今天的每日一题是LC406 根据身高重建队列,属于贪心算法的一题，以此记录解题思路。

描述

题目描述如下：

假设有打乱顺序的一群人站成一个队列。每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。编写一个算法来重建这个队列。
1
2
3
4
5
6
7
示例

输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

分析

完成这题最主要的就是要明白每个元素顺序对k的影响。

1.首先将元素排序。$h$大的放在前面，如果$h$相同，则把$k$大的放前面。

2.将排序后的元素放入队列中。

第 $0, \cdots, i-10,⋯,i−1 $个人已经在队列中被安排了位置，他们只要站在第 $i$ 个人的前面，就会对第 $i$ 个人产生影响，因为他们都比第 $i$ 个人高；

而第 $i+1, \cdots, n-1$ 个人还没有被放入队列中，并且他们无论站在哪里，对第 $i$ 个人都没有任何影响，因为他们都比第 $i$ 个人矮。

也就是说，当我们放入第 $i$ 个人时，只需要将其插入队列中，使得他的前面恰好有 $k_i$ 个人即可。

代码

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


/*
 * @lc app=leetcode.cn id=406 lang=cpp
 *
 * [406] 根据身高重建队列
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution {
 public:
  vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    sort(people.begin(), people.end(),
         [](const vector<int>& u, const vector<int>& v) {
           return u[0] > v[0] || (u[0] == v[0] && u[1] < v[1]);
         });

    vector<vector<int>> ans;
    for (const vector<int>& person : people) {
      ans.insert(ans.begin() + person[1], person);
    }
    return ans;
  }
};
// @lc code=end

参考

题解

LC406 根据身高重建队列