讲个让人又无语又想笑的事情——同事在会议室被领导“亲自指导”了一顿，直接扇了好几个大嘴巴子。🫣
你们说，这事儿能不离谱吗？领导一顿“教育”之后，同事竟然淡定地说：“发疯真的很爽，感觉自己不活了，谁也别想活。”然后，还开玩笑说下次如果再被逼疯，直接扇领导几个耳光。😂
这，简直就是我辈楷模呀，让领导直接傻眼，无路可走了。
我觉得吧，这种事儿虽然荒唐，但也能看出一位“程序员”面对职场压力时的无奈。
老实说，有时候工作中的小问题被夸大成大问题，真的是让人想不发火都难！不过，扇耳光的方式...就算了吧，毕竟这年头，我们不是都应该尽量避免“硬碰硬”嘛？
算法题：根据身高重建队列
今天咱们来聊一个经典的面试题：根据身高重建队列。面试官提问的时候通常会要求你用O(n log n) 或者O(n) 的时间复杂度来解决，为什么？因为这题的本质就考你如何巧妙地利用数据结构和算法的特性，把复杂度控制在一个合理的范围内。
题目描述：
你有一个队列，里面每个人都有两个属性：身高h和前面有多少人比他高（这个数字叫做k）。我们需要根据这些信息重新排列队列，保证每个人前面有k个比他高的人。
在这类题目里，我们通常需要借助排序和数据结构的组合。咱们来看一下这道题怎么解决。
思路
排序：
首先，我们需要对这些人按照身高进行排序。排序的顺序很重要——我们先将身高从高到低排，原因很简单：越高的人，他前面要排的位置要求越严格。而相对较矮的人，由于前面高的人数量较少，他们的安排灵活性更大。这样，我们可以通过排序来缩小每个人前面有多少人比他高的“约束”，然后根据每个人的
k值插入合适的位置。插入位置：
排完序后，遍历这个队列，针对每个人，直接将其插入到合适的位置。由于前面有k个人比他高，所以对于每个人来说，k就是他的插入位置。
步骤
按身高降序排列：
先将所有人按照身高降序排列，身高相同的情况下再按照k值升序排列。身高高的人先插入，能保证他们的k值更容易满足。插入到指定位置：
我们维护一个空队列，遍历排序后的列表，依次将每个人插入到队列中的位置。这一过程通过使用List的add(index, element)方法来完成，这样可以直接按照k值插入。
代码实现
这里我们用Java实现一下这个算法：
import java.util.*;
class Person {
int height;
int k;
Person(int height, int k) {
this.height = height;
this.k = k;
}
}
public class QueueReconstruction {
public int[][] reconstructQueue(int[][] people) {
List<Person> list = new ArrayList<>();
// 将输入数组转换为Person对象数组
for (int[] p : people) {
list.add(new Person(p[0], p[1]));
}
// 按照身高降序，身高相同的按k值升序排序
Collections.sort(list, (a, b) -> a.height != b.height ? b.height - a.height : a.k - b.k);
// 构建最终的队列
List<Person> result = new ArrayList<>();
for (Person p : list) {
result.add(p.k, p); // 根据k值插入到正确的位置
}
// 将结果转回数组形式
int[][] resultArr = new int[people.length][2];
for (int i = 0; i < result.size(); i++) {
resultArr[i][0] = result.get(i).height;
resultArr[i][1] = result.get(i).k;
}
return resultArr;
}
public static void main(String[] args) {
QueueReconstruction qr = new QueueReconstruction();
// 测试数据
int[][] people = {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};
int[][] result = qr.reconstructQueue(people);
// 输出结果
for (int[] person : result) {
System.out.println(Arrays.toString(person));
}
}
}
解释
排序：我们先按身高降序排列。如果身高相同， k值小的排前面，这样确保我们插入时能够更容易满足前面有k个人比自己高的条件。插入：我们遍历排序后的队列，对于每个人，按照他的 k值插入到队列中指定的位置，这样可以确保每个人前面正好有k个比他高的人。
时间复杂度
排序： O(n log n)，因为我们对所有人按身高进行排序。插入： O(n)，每个人插入的时间复杂度是O(n)，但是每个人只能插入一次。
因此，整体的时间复杂度是O(n log n)，这是最优化的解法。
对编程、职场感兴趣的同学，可以链接我，微信：coder301 拉你进入“程序员交流群”。
