406. 根据身高重建队列

这一题的思路是排队加插队,还有就是高的人的位置不会因为低的人的位置所影响

首先我们要根据每个人的身高降序排序,然后根据每个人的k值升序排序,也就是高的人在前面,有k值单身高相等的人应该排在没k值身高相等的人的后面

这样完成了排队,接下来就是插队,先排的一定是高的人,因为高的人不会收到影响,但是低的人会被影响,插队这里使用了LinkedList,这是因为要频繁的在中间位置插入数据,所以不使用ArrayList

插队完转化成数组即可

class Solution { public int[][] reconstructQueue(int[][] people) { //先根据身高降序排序,如果身高相同按照k值升序排序 Arrays.sort(people, (a, b) ->{ if (a[0] != b[0]) return b[0] - a[0]; return a[1] - b[1]; }); List<int[]> list = new LinkedList<>(); //遍历出每个人 for (int[] p : people) { list.add(p[1], p); } return list.toArray(new int[people.length][]); } }