題目

https://leetcode.com/problems/queue-reconstruction-by-height/

題解

思路：先排序，后插入。

看到 答案 中的一句話，恍然大悟了：
第 i 個(gè)人的位置，就是隊(duì)列中從左往右數(shù)第 ki+1 個(gè)「空」位置。（空位置用來安排給后面身高更高的人，身高相同的人也參與空位置的計(jì)數(shù)）

我自己怎么想不出來呢…

class Solution {public int[][] reconstructQueue(int[][] people) {// sortint[][] res = new int[people.length][2];boolean[] free = new boolean[people.length];Arrays.fill(free, true);Arrays.sort(people, new Comparator<int[]>() {@Overridepublic 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) {// 前面累計(jì)k個(gè)空位置int empty = 0;int j;for (j = 0; j < people.length && empty < p[1]; j++) {if (free[j] || res[j][0] == p[0]) empty++;}// 放在下一個(gè)空位置上while (j < people.length) {if (free[j]) {res[j][0] = p[0];res[j][1] = p[1];free[j] = false;break;}j++;}}return res;} }

總結(jié)

以上是生活随笔為你收集整理的leetcode 406. Queue Reconstruction by Height | 406. 根据身高重建队列（Java）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。