leetcode 406. Queue Reconstruction by Height | 406. 根据身高重建队列（Java）

╰半橙微兮° 2022-08-29 10:15 124阅读 0赞

## 题目 ##

[https://leetcode.com/problems/queue-reconstruction-by-height/][https_leetcode.com_problems_queue-reconstruction-by-height]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

思路：先排序，后插入。

看到 [答案][Link 1] 中的一句话，恍然大悟了：  
**第 i 个人的位置，就是队列中从左往右数第 ki+1 个「空」位置。**（空位置用来安排给后面身高更高的人，身高相同的人也参与空位置的计数）

我自己怎么想不出来呢…

class Solution { 
        public int[][] reconstructQueue(int[][] people) { 
            // sort
            int[][] res = new int[people.length][2];
            boolean[] free = new boolean[people.length];
            Arrays.fill(free, true);
            Arrays.sort(people, new Comparator<int[]>() { 
                @Override
                public int compare(int[] o1, int[] o2) { 
                    if (o1[0] != o2[0]) return o1[0] - o2[0];
                    else return o1[1] - o2[1];
                }
            });
    
            for (int[] p : people) { 
                // 前面累计k个空位置
                int empty = 0;
                int j;
                for (j = 0; j < people.length && empty < p[1]; j++) { 
                    if (free[j] || res[j][0] == p[0]) empty++;
                }
                // 放在下一个空位置上
                while (j < people.length) { 
                    if (free[j]) { 
                        res[j][0] = p[0];
                        res[j][1] = p[1];
                        free[j] = false;
                        break;
                    }
                    j++;
                }
            }
            return res;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_queue-reconstruction-by-height]: https://leetcode.com/problems/queue-reconstruction-by-height/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/b38d1a69957946b88ade0dd43699e496.png
[Link 1]: https://leetcode-cn.com/problems/queue-reconstruction-by-height/solution/gen-ju-shen-gao-zhong-jian-dui-lie-by-leetcode-sol/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/6569eb3247a747c9b8399e7a71db73fe.png