406. 根据身高重建队列

题目

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例 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]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例 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
题目数据确保队列可以被重建

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/queue-reconstruction-by-height
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

因为和前面比较的是身高h不小于自己的，那么优先排高个子可以确保之后的低个子无论排在哪里都不影响高个子。如果h相同，需要优先排列较小的k才可以满足条件。

那么可以对数组进行排序，按h降序、k升序排列。排好序后进行遍历，进一步调整，将每个人插入在k下标处。见代码一。

代码

代码一 身高从大到小考虑(贪心) O(n^2)

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (p1, p2) -> p1[0] == p2[0] ? p1[1] - p2[1] : p2[0] - p1[0]);
        List<int[]> list = new LinkedList<>();
        for(int[] p : people){
            list.add(p[1], p);
        }
        return list.toArray(new int[list.size()][2]);
    }
}

代码二 身高从小到大考虑 O(n^2)

也可以按身高从小到大考虑，h升序k降序排列，参考「这个」思路。

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (p1, p2) -> p1[0] == p2[0] ? p2[1] - p1[1] : p1[0] - p2[0]);
        int n = people.length;
        int[][] ans = new int[n][2];
        // id[i]数组用来标记第i个位置是否已经站了人
        int[] id = new int[n];
        for (int[] p : people) {
            int i = -1;
            int cnt = 0;
            // 前面要有p[1]个人身高不小于自己，那么需要找到第p[1]+1(从1开始数)个空余位置
            while (cnt < p[1] + 1) {
                // i先++，后加的话会多1，那样需要使用break
                i++;
                if (id[i] == 0) {
                    cnt++;
                }
            }
            id[i] = 1;
            ans[i] = p;
        }
        return ans;
    }
}

代码三 二分+树状数组优化代码二 O(nlog(n)log(n))

代码二中每次找空余的第k个位置都要线性查找，使整体代码时间最坏降到#card=math&code=O%28n%5E2%29&id=PMKkH)，故考虑优化。

id数组某一位置之前的空余数目可以用当前下标+1再减去前面被占的数目，后者可以使用前缀和获得。而id数组是不断变化的，维护动态的前缀和是树状数组所擅长的。

想要获得第(p为people中的数组)个空余位置，可以外层使用二分，因为当mid左侧空余数不够时，就可以排除左侧，因此可以使用二分。

二分内部求左侧空余数时，可以使用树状数组维护动态的前缀和。

整体时间复杂度从#card=math&code=O%28n%5E2%29&id=Ev015)降到了)#card=math&code=O%28nlog%5E2%28n%29%29&id=U0QWJ)，具体细节见代码注释。

后来又了解到可以直接在树状数组上进行二分，省去一个log时间复杂度，后面有时间学习吧，真的学无止境啊哈哈。

class Solution {
    int[] id;
    int n;
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (p1, p2) -> p1[0] == p2[0] ? p2[1] - p1[1] : p1[0] - p2[0]);
        n = people.length;
        id = new int[n + 1];
        int[][] ans = new int[n][2];
        for (int[] p : people) {
            int l = 0;
            int r = n - 1;
            // 使用二分在空余的位置中找第p[0]+1个
            while (l < r) {
                int mid = l + (r - l) / 2;
                // k为mid下标左侧被占用的位置数目，mid+1-k就是空余数目，需要和p[1]+1比较，两者都有1，因此下面消掉了
                int k = query(mid + 1);
                // mid左侧空余数不够p[1]+1，因此mid肯定不是要找的第p[1]+1个位置，只能往右找了
                if (mid - k < p[1]) {
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }
            // 将id[l]改为1，标记l位置被占用
            update(l + 1, 1);
            // 将当前p放在l位
            ans[l] = p;
        }
        return ans;
    }
    public void update(int i, int delta) {
        while (i <= n) {
            id[i] += delta;
            i += lowbit(i);
        }
    }
    public int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += id[i];
            i -= lowbit(i);
        }
        return sum;
    }
    public static int lowbit(int x) {
        return x & (-x);
    }
}