406. 根据身高重建队列(leetcode)
https://leetcode.cn/problems/queue-reconstruction-by-height/submissions/
贪心:大致思路是排序,但是可以先排k再排h,或者是先排h再排k,这里只能穷举,发现第一种不合法
于是使用第二种,先按照h排序,然后由于h有序了(从大到小降序),因此后序再排k时,后面的数根据k来向前移动并不影响k的正确性,即前面有k个数比此数大的概念
class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people,(a,b)->{
if(a[0]==b[0])return a[1]-b[1]; // h相同按照k升序
return b[0]-a[0]; // 按h降序排序
});
LinkedList<int[]> que = new LinkedList<>();
// 按照k作为下标逐一插入,并不影响k的正确性
for (int[] p : people) {
que.add(p[1],p); //Linkedlist.add(index, value)，value插入到指定index
}
return que.toArray(new int[people.length][]);
}
}