题目描述

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。

编写一个算法来重建这个队列。总人数少于1100人，假设输入合法。

样例

Example 1:

输入: [[2,1],[3,3],[5,0],[7,0],[4,2]]
输出: [[5,0],[2,1],[7,0],[4,2],[3,3]]

算法1

(排序 + 策略) $O(n^2)$

最开始队列是空的，队列状态为[0,0,0,0,0](0表示这个位置空着)。

首先我们考虑最矮的那个人，例如样例里的[2,1]，排在最矮的人前面的人都会比最矮的人高，因此最矮的人会排在第k+1位（前面的k个人都比自己高），因此我们确定了[2,1]的排位是第二个，这时候队列状态变为[0,1,0,0,0]（1那里是被[2,1]给占了）

然后我们考虑第二矮的人，即[3,3]，所有人里除了高度为2的人，其他人都比[3,3]这个人高，因此只能从剩下能排的位置里选排在第4个的，因此这时候队列状态变为了[0,1,0,0,1]（后面的1就是被[3,3]给占了）

依次类推，因此我们先对高度进行从小到大排序，先对矮的人，放到当前空闲的第k+1位，然后将该位置设为非空闲，更新队列状态，再排下一个人即可。特别需要注意的是排序时当两个人的身高相同时，按k从大到小的顺序进行排序。

时间复杂度

对每个人都要遍历一遍当前队列，找空闲的第k+1位，因此是$(n^2)$的复杂度

Python 代码

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people = sorted(people, key = lambda d:(d[0], -d[1]))
        queue = [None for _ in range(len(people))] # None表示这个位置还空闲着

        for h, k in people:
            available_cnt = 0
            for i in range(len(queue)):
                if queue[i] is None:
                    available_cnt += 1
                if available_cnt == k + 1:
                    queue[i] = (h, k)
                    break

        return queue

算法2

(二分 + 树状数组) $O(n\*logn\*logn)$

算法1中我们每次需要找当前可用的第k+1个是通过遍历队列数组来找到的，可以考虑用二分+树状数组优化。

起始状态queue的值为0，每次占用了一个位置，则当前位置的值+1，二分找p，使得queue[0:p]的前缀和为p - (k + 1)（即1-p一共有p个位置，被占用了sum(queue[0:p])个位置，还剩下p - sum(queue[0:p]) = k + 1个可用位置。

Python 代码

class BIT:
    def __init__(self, n):
        self.c = [0 for _ in range(n)]

    def low_bit(self, p):
        return p & -p

    def add(self, p, v):
        while p < len(self.c):
            self.c[p] += v
            p += self.low_bit(p)

    def get_sum(self, p):
        s = 0
        while p > 0:
            s += self.c[p]
            p -= self.low_bit(p)
        return s

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people = sorted(people, key = lambda d:(d[0], -d[1]))
        tree = BIT(len(people) + 1)

        queue = [None for _ in range(len(people))]
        for h, k in people:
            l, r = 1, len(queue) # 二分搜最终位置
            while l < r:
                mid = (l + r) // 2
                if mid - tree.get_sum(mid) < k + 1:
                    l = mid + 1
                else:
                    r = mid
            tree.add(l, 1) # 表示占用了位置l
            queue[i] = (h, k)

        return queue

算法3

(贪心 + 堆) $O(n^2)$

首先考虑最终队列排在第一个的人，这个人的k肯定为0。 考虑所有k=0的人，只有两种情况，要么是自己本身就排在第一个，要么是自己足够高到比排在前面的人都要高。这些人里面最矮的那个肯定排在队列第一个，例如例子里的[7,0], [5,0]两个人的k都是0，那么[5,0]肯定是排在第一个的人，因此我们可以发现结论

对于k=0的人，最矮的那个就是当前排在最前面的人。

确定了[5,0]排在最前面后，那些比5矮的人，即[2,1],[3,3],[4,2]这些人都排在5后面，对[2,1]来说，已经找到了排在前面且比自己高的唯一的那个人了（就是第一位的5）。我们将k’定义为未知的排在自己前面且比自己高的人的数量，因此[2,1]这个人的k’变为了0，这个人可以进入我们的考虑范围内了，因为他前面没有别的比自己高的人了，这时候我们要排第二个人，那么就是从我们发现当前k’=0的只有[7,0]和[2,1]这两个人，因此我们选矮的那个，即[2,1]，因此确定了[2,1]排在第二位。之后以此类推即可。

因此我们会发现策略，就是将k'=0的人放入最小堆里，弹出堆顶最矮的那个人放到最后结果的队列里，同时将那些还不确定位置的人里更矮的人的k'-1，更新这些人的k’并将k'=0的人入堆。（很类似于拓扑排序）

时间复杂度

由于弹出每个人后都需要遍历一遍队列，将比自己矮的且k’>0的人的k’-1，因此是$O(n^2)$的复杂度

Python 代码

import heapq
class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        heap = []
        people_t = []
        for i in range(len(people)):
            h, k_t = people[i]
            if k_t == 0: # k’=0的入堆
                heapq.heappush(heap, (h, i))
            people_t.append([h, k_t]) # 这里的k_t就是k‘

        res = []
        while len(heap) > 0:
            h, idx = heapq.heappop(heap)
            res.append(people[idx]) # 将people[idx]这个人放入最后结果的队列里
            for i in range(len(people_t)):
                if people_t[i][0] <= h and people_t[i][1] > 0:
                    people_t[i][1] -= 1 # k'-1
                    if people_t[i][1] == 0: # k'=0的人入堆
                        heapq.heappush(heap, (people_t[i][0], i))

        return res