LeetCode刷题：贪心算法 [406.根据身高重建队列] - Java版本

LeetCode刷题：贪心算法 [406.根据身高重建队列] - Java版本

贪心算法：区间问题

只是记录自己的刷题过程，答案参考过多种题解。

如有错误感谢指正！

参考：① LeetCode 101: A LeetCode Grinding Guide (C++ Version) 作者：高畅 Chang Gao

           ② 代码随想录 (programmercarl.com) 作者：程序员Carl

题目来源：题库 - 力扣 (LeetCode) 全球极客挚爱的技术成长平台 (leetcode-cn.com)

406.根据身高重建队列 (Medium)

• 本题有两个维度，h和k，看到这种题目一定要想如何确定一个维度，然后在按照另一个维度重新排列。如果两个维度一起考虑一定会顾此失彼。

• 思路是先给最低的人安排位置，他前面有多少个人比他高则在前面多少个空位置以容纳这些人，自己则在这些空位后的第一个空位上。

• 先按照身高从大到小 排序 之后，优先按身高高的people的k来 插入 ，后序插入节点也不会影响前面已经插入的节点（矮个的插入不会影响原本高个的排序），最终按照k的规则完成了队列。

• 局部最优：优先按身高高的people的k来插入。插入 *** 作过后的people满足队列属性。

• 全局最优：最后都做完插入 *** 作，整个队列满足题目队列属性。

public int[][] reconstructQueue(int[][] people) {
    // 身高从大到小排（身高相同 k小的站前面）
    Arrays.sort(people, (a, b) -> {
        if (a[0] == b[0]) {
            return a[1] - b[1]; //第一个元素(身高)相等时，第二个元素(个数)升序
        }
        return b[0] - a[0]; //第一个元素(身高)不相等时，第一个元素(身高)降序
    });
    ArrayList que = new ArrayList<>();
    for (int[] p : people) {
        que.add(p[1],p); //p[1]代表取每个数组p对应的第二位元素的数值(个数)，即要插入的下标
    }
    return que.toArray(new int[people.length][]);
}

---

补充知识：Arrays.sort()的运用​

方法一：

Arrays.sort(arr);

方法二：

Arrays.sort(arr,startIndex,endIndex); // 不包含endIndex这个索引值

方法三：

Arrays.sort(people, new Comparator() {
    @Override
    public int compare(int[] person1, int[] person2){
        if (person1[0] != person2[0]){
            //第一个元素不相等时，第一个元素降序
            return person2[0] - person1[0];
        }else{
            //第一个元素相等时，第二个元素升序
            return person1[1] - person2[1];
        }
    }
});

方法四：

Arrays.sort(people,(person1,person2)->{
    if(person1[0]!=person2[0]){
        return person2[1]-person1[1];
    }else{
        return person1[1]-person2[1];
    }
]);

方法3和方法4都是一样的，只是在自定义比较的时候语法有点区别。 另外根据return的值可以分为：

（1）一个正数时：交换位置；

（2）一个负数时：位置不变；

（3）0：此时两个值相等，位置交换和保持都一样。

• 升序：compare1 - compare2;

• 降序：compare2 - compare1。