LeetCode 406. 根据身高重建队列思路排序 插入关键观察· 如果按身高从高到低排序那么处理当前人时已排好的人都不比当前人矮。· 因此当前人 [h, k] 直接插入到位置 k前面恰好有 k 个人比他高或等高完全满足条件。· 身高相同时k 小的排前面k 小的应该靠前先插入不会影响 k 大的。排序规则h 降序k 升序然后依次 list.add(p[1], p) 插入。Java 实现classSolution{publicint[][]reconstructQueue(int[][]people){// 身高降序k 升序Arrays.sort(people,(a,b)-{if(a[0]!b[0])returnb[0]-a[0];returna[1]-b[1];});Listint[]listnewArrayList();for(int[]p:people){list.add(p[1],p);}returnlist.toArray(newint[people.length][]);}}复杂度· 时间O(n²)排序 O(n log n) 每次插入 O(n)· 空间O(n)测试样例SolutionsnewSolution();int[][]p1{{7,0},{4,4},{7,1},{5,0},{6,1},{5,2}};System.out.println(Arrays.deepToString(s.reconstructQueue(p1)));// [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]int[][]p2{{6,0},{5,0},{4,0},{3,2},{2,2},{1,4}};System.out.println(Arrays.deepToString(s.reconstructQueue(p2)));// [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]关键点易错点 说明排序规则 身高降序、k 升序不能反相同身高 k 小的先插入k 大的插入不会挤掉正确位置插入位置 直接插到下标 p[1]无需调整add vs set 用 add(index, p) 插入不是覆盖优化思路可选ArrayList.add(index, …) 每次是 O(n) 移动。若追求 O(n log n)可用· 树状数组 / 线段树 二分从矮到高处理找第 k 个空位· 或 LinkedList但随机插入仍需遍历实际更慢面试中标准 O(n²) 解法即可思路清晰最重要。