406. 根據(jù)身高重建隊(duì)列。

假設(shè)有打亂順序的一群人站成一個(gè)隊(duì)列，數(shù)組 people 表示隊(duì)列中一些人的屬性（不一定按順序）。每個(gè) people[i] = [hi, ki] 表示第 i 個(gè)人的身高為 hi ，前面 正好 有 ki 個(gè)身高大于或等于 hi 的人。

請(qǐng)你重新構(gòu)造并返回輸入數(shù)組 people 所表示的隊(duì)列。返回的隊(duì)列應(yīng)該格式化為數(shù)組 queue ，其中 queue[j] = [hj, kj] 是隊(duì)列中第 j 個(gè)人的屬性（queue[0] 是排在隊(duì)列前面的人）。

示例 1：

輸入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
輸出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解釋：
編號(hào)為 0 的人身高為 5 ，沒(méi)有身高更高或者相同的人排在他前面。
編號(hào)為 1 的人身高為 7 ，沒(méi)有身高更高或者相同的人排在他前面。
編號(hào)為 2 的人身高為 5 ，有 2 個(gè)身高更高或者相同的人排在他前面，即編號(hào)為 0 和 1 的人。
編號(hào)為 3 的人身高為 6 ，有 1 個(gè)身高更高或者相同的人排在他前面，即編號(hào)為 1 的人。
編號(hào)為 4 的人身高為 4 ，有 4 個(gè)身高更高或者相同的人排在他前面，即編號(hào)為 0、1、2、3 的人。
編號(hào)為 5 的人身高為 7 ，有 1 個(gè)身高更高或者相同的人排在他前面，即編號(hào)為 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新構(gòu)造后的隊(duì)列。

示例 2：

輸入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
輸出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

提示：

1 <= people.length <= 2000
0 <= hi <= 10^6
0 <= ki < people.length
題目數(shù)據(jù)確保隊(duì)列可以被重建

算法分析

解題思路

• 先排序，h升序,k降序
• 根據(jù)k值站位

class Solution {public int[][] reconstructQueue(int[][] people) {//h升序,k降序Arrays.sort(people, (o1,o2) -> o1[0] != o2[0] ? o2[0]- o1[0] : o1[1] - o2[1]);List<int[]> ans = new ArrayList<int[]>();for (int[] person : people) {ans.add(person[1], person);}return ans.toArray(new int[ans.size()][]);}
}

復(fù)雜性分析

時(shí)間復(fù)雜度：O(n2)
空間復(fù)雜度：O(logn)