406-Queue-Reconstruction-by-Height

TAG: 贪婪

原题

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:
The number of people is less than 1,100.

Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

思路

先思考大家高度都是一样的情况，比如[7,0]和[7,1]这样两个人，正确的排序方法就是让k更大的人往后排。

这时，我们推广一下，如果加入一个更矮的人，比如[6,1]，那么他应该放哪里呢，显然应该放在[7,0]和[7,1]之间，最后形成了[7,0][6,1][7,1]这样的序列。

如果我们加入一个更高的人呢？比如[8,0]，显然要构成[7,0][7,1][8,0]

通过观察我们可以发现，插入更矮的人，是不会改变已经按高度排好队的序列的，只是更矮的人会插入到这些人之间，再思考一下，矮的人要插入到什么位置呢？

由于条件限制，k所表示的是这个人前面有几个人，k=1，前面有1个，k=2，前面有两个。

综合以上，当我们在一个按高度排序好的队列中，插入一个更矮的人，就直接放在第k个位置上。

这样，我们就可以将原来的数组，先按高度h逆序排（高个子的在前面），然后再按k顺序排。

然后，再建立一个新的数组，依次的从排好的原数组中取出元素，插入到当前项的第k个位置上。

想想看，第一个插入进来的，一定是最高的那个[8,0]，它左边的人最少（为0），第二个插入进来的，一定是和第一个人一样高或者矮于第一个人的人，它的k一定是1。8,0

第三个人如果更加矮，因为现在数列中有两个人了，k必然是1，或者2，否则的话，题目给的数据就是错的，无法正确的处理了。

可以继续推理下去……

要是还是没有理解，可以再参考一下原题的解答：406. Queue Reconstruction by Height

这道题是属于那种没有思路真是难想出来的那种

代码如下：

public int[][] reconstructQueue(int[][] people) {
    Arrays.sort(people, new Comparator<int[]>() {

        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0];
        } 
    });

    List<int[]> output = new LinkedList();
    for (int[] p : people) {
        output.add(p[1], p);
    }
    return output.toArray(new int[people.length][2]);
}

更多干货内容，欢迎关注我的公众号：好奇码农君
关注了之后就可以在手机上随时随地查看文章啦