Leetcode 406 根据身高重建队列

题意理解：

????????people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

? ? ? ? 给定一个二维数组，（h,k）h表示此人身高，k表示前面有几个人比他高。

? ? ? ? 我们按照每个人的h,k两个维度的需求给每个人排在合适的位置。

? ? ? ? 如：

? ? ? ? ? ? ? ? [5,0][7,0][5,2][6,1][4,4][7,1]

????????

解题思路：

? ? ? ?采用贪心思路来解题，明确全局最优和局部最优。

? ? ? ?全局最优：每个人的位置满足其h,k的需求。

? ? ? ?对于每个人的位置，我们需要考虑两个维度。

? ? ? ?对于需要考虑多个维度的题目，我们可以逐个考虑，减小难度。

? ? ? ?1.首先考虑k维度。我们将k从小到大排，k相同时，h从小到大排。

? ? ? ? 所以有：

? ? ? ? ? ? ? ? [5,0][7,0][6,1][7,1][5,2][4,4],其中[5,2],[4,4]位置错误

? ? ? ? 2.考虑h维度，将h从大到小排，h相同时，k从小到大排。

? ? ? ? 所以有：

? ? ? ? ? ? ? ? [7,0][7,1],[6,1][5,0],[5,2][4,4]

? ? ? ? 我们发现：

? ? ? ? ? ? ? ? 身高高的总是在前面，当一个元素如[6,1]前面比它大的多的时候，需要将其往前移

? ? ? ? ? ? ? ? 因为前面每一个数都比他大，多以，一枝位置1处，其余后移即可。

????????????????其前面满足条件的并不会因为一个身高比他们都低的人加入，而不满足其位置条件。

? ? ? ? ? ? ? ? 依次类推：我们获得最终结果：

????????????????????????[5,0][7,0][5,2][6,1][4,4][7,1]

? ? ? ? 所以局部最优即：将身高最高的人，优先安排合理的位置。

1.贪心解题

我们用result来记录结果。在处理问题之前，我们需要首先根据身高从大到小排序，身高相同时，根据k升序排序。

public int[][] reconstructQueue(int[][] people) {
        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[]> result=new LinkedList<>();

        for(int i=0;i<people.length;i++){
            int position=people[i][1];
            result.add(position,people[i]);
        }
        //转数组
        return result.toArray(new int[people.length][]);
    }

2.分析?

时间复杂度：O()? 排序所需时间O(nlogn)+遍历插入O()

空间复杂度：O(nlogn) 排序所需的栈空间

n为输入数组长度。