How do I efficiently reconstruct the queue by height?

Sort the people array by height in descending order, and then use a binary indexed tree to efficiently track available positions while placing people.

What is the role of the binary indexed tree in this problem?

The binary indexed tree (BIT) is used to track available positions in the queue and ensures efficient placement of each person based on the number of taller people already in front.

How does the sorting step help in reconstructing the queue?

Sorting the array by height first ensures that the tallest people are placed first, and the secondary sorting by the number of taller people in front guarantees the correct position for each person.

What is the time complexity of the solution?

The time complexity is O(n log n) due to the sorting and binary indexed tree operations, where n is the number of people in the input array.

Can the queue reconstruction be done without sorting?

No, sorting by height is crucial to ensure the correct order of placement, especially when handling multiple people of the same height.

#406

Medium

auto_awesome数组·结合·二分·indexed·树

LeetCode 题解工作台

根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [h i , k i ] 表示第 i 个人的身高为 h i ，前面正好有 k i 个身高大于或等于 h i 的人。请你重新构造并返回输入数组 people 所表示的队列…

数组树状数组线段树排序

题目描述

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

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [h_j, k_j] 是队列中第 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 <= h_i <= 10⁶
0 <= k_i < people.length
题目数据确保队列可以被重建

lightbulb

解题思路

方法一

1

2

3

4

5

6

7

8

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x: (-x[0], x[1]))
        ans = []
        for p in people:
            ans.insert(p[1], p)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of sorting and binary indexed trees.
question_mark
Check if the candidate can explain the interaction between sorting and efficient placement using BIT.
question_mark
Evaluate how the candidate optimizes for time complexity, particularly with larger inputs.

warning

常见陷阱

外企场景

error
Not understanding the need for sorting the array by height before inserting people into the queue.
error
Failing to use the binary indexed tree efficiently for tracking available positions.
error
Inserting people into incorrect positions due to not properly considering the 'k' value in the sorting step.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Changing the sorting order of people, such as sorting by height in ascending order first.
arrow_right_alt
Optimizing the binary indexed tree for different constraints or array sizes.
arrow_right_alt
Modifying the problem by including additional attributes for each person, such as age, to be taken into account during the reconstruction.

help

常见问题

外企场景

继续练习

#327 区间和的个数 #493 翻转对 #315 计算右侧小于当前元素的个数