贪心算法解决根据身高重建队列问题
代码随想录链接:代码随想录
思路:
本题有两个维度h和k，一定要想如何确定一个维度，然后再按照另一个维度重新排列
首先根据第一个维度h对原数组进行排序，让身高高的元素尽量排在数组前端
之后根据每个元素的第2个维度k确定该元素的插入位置，将该元素插入到位置k处
局部最优:优先按身高高的people的k来插入。插入操作过后的people满足队列属性
全局最优:最后都做完插入操作，整个队列满足题目队列属性
class Solution {
public int[][] reconstructQueue(int[][] people) {
// 身高从大到小排（身高相同k小的站前面）
Arrays.sort(people, (a, b) -> {
if (a[0] == b[0]) return a[1] - b[1]; // a - b 是升序排列，故在a[0] == b[0]的狀況下，會根據k值升序排列
return b[0] - a[0]; //b - a 是降序排列，在a[0] != b[0]，的狀況會根據h值降序排列
});
LinkedList<int[]> que = new LinkedList<>();
for (int[] p : people) {
que.add(p[1],p); //Linkedlist.add(index, value)，會將value插入到指定index裡。
}
return que.toArray(new int[people.length][]);
}
}