Leetcode 406. 根据身高重建队列

1.题目基本信息

1.1.题目描述

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [h_i, k_i] 表示第 i 个人的身高为 h_i ，前面 正好 有 k_i 个身高大于或等于 h_i 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [h_j, k_j] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

题目意思: 原本有个排列正确的队列，现在被打乱成了people，现在需要我们根据打乱的people数列恢复之前正确的队列

1.2.题目地址

https://leetcode.cn/problems/queue-reconstruction-by-height/description/

2.解题方法

2.1.解题思路

本题只看官方题目，比较不太好理解。但是通过案例理解就很好理解。本质就是：原本有个排列正确的队列，现在被打乱成了people，现在需要我们根据打乱的people数列恢复之前正确的队列。 理解题意后，直接排序、遍历就很容易了

2.2.解题步骤

第一步，将people按身高升序、高于人数降序进行排列

第二步，初始化返回数组。并遍历people，每遍历一次的结果是在result中填上一个空位。对于遍历的第一个person，其余的length-1的人身高均大于或等于其，所以只需填到peroson[1]+1个空位处即可；对于后面person，第person[1]+1个空位也是合法位置（注意：对于当前遍历的person，前面的部分坑已经被前面遍历的填了）。最后，对于一种特殊情况的解释，就是相同身高但是person[1]不同的人，这种通过person[1]多的人先遍历，避免了对person[1]少的人的填坑的影响。

3.解题代码

Python代码

# 题目意思: 原本有个排列正确的队列，现在被乱成了people，现在需要我们根据打乱的people数列恢复之前正确的队列
class Solution:def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:length=len(people)# 第一步，将people按身高升序、高于人数降序进行排列people.sort(key=lambda person:[person[0],-person[1]])# 第二步，初始化返回数组。并遍历people，每遍历一次的结果是在result中填上一个空位。对于遍历的第一个person，其余的length-1的人身高均大于或等于其，所以只需填到peroson[1]+1个空位处即可；对于后面person，第person[1]+1个空位也是合法位置（注意：对于当前遍历的person，前面的部分坑已经被前面遍历的填了）。最后，对于一种特殊情况的解释，就是相同身高但是person[1]不同的人，这种通过person[1]多的人先遍历，避免了对person[1]少的人的填坑的影响。result=[[] for _ in range(length)]for person in people:blankPosCnt=person[1]+1for i in range(length):if not result[i]:blankPosCnt-=1if blankPosCnt==0:result[i]=personbreakreturn result                

C++代码

class Solution {
public:vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {int length=people.size();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>> result(length);for(auto person:people){int blankPosCnt=person[1]+1;for(int i=0;i<length;++i){if(result[i].empty()){blankPosCnt--;if(blankPosCnt==0){result[i]=person;break;}}}}return result;}
};

4.执行结果