# 406 Queue Reconstruction by Height

## 406. [Queue Reconstruction by Height](https://leetcode.com/problems/queue-reconstruction-by-height/description/)

## 1. Question

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers`(h, k)`, where`h`is the height of the person and`k`is the number of people in front of this person who have a height greater than or equal to`h`. Write an algorithm to reconstruct the queue.

**Note:**\
The number of people is less than 1,100.

**Example**

```
Input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
```

## 2. Implementation

**(1) Sorting** 

思路:

(1) 根据题意，我们发现两点:1.最矮的人不会影响其他人的位置, 2. 在最矮的人群中，k的值最高的那个人不会影响其他人的位置。

(2) 基于这两点，我们可以将输入数组按照以下规则排序，先按高度从高到低排， 如果高度相同，则将index(第二个元素)的数从小到大排，排好序后，第二个元素则为该数组所处的位置

```java
class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[0] == b[0] ? a[1] - b[1] : b[0] - a[0];
            }
        });

        List<int[]> list = new ArrayList<>();

        for (int[] info : people) {
            list.add(info[1], info);
        }

        int[][] res = new int[people.length][2];

        for (int i = 0; i < people.length; i++) {
            res[i][0] = list.get(i)[0];
            res[i][1] = list.get(i)[1];
        }
        return res;
    }
}
```

**(2) Binary Search Tree**

1.第一步还是先对people数组排序，将高的排在前面，同样高度的话按照第二元素的值升序排。

2.第二步自定义Binary Search Tree， treeNode包含leftCount代表对当前node里的这个人有多少人是比他高。由于我们是按照高度从高到矮插入bst中，所以对于当前要插入的node(这个node代表的人的高度必然不比当前bst每个node个高度高)，如果它的k值(每个数组第二个元素)比curNode的leftCount小，说明curNode代表的人的高度不会影响要插入node的位置，所以node要在curNode的左边，否则node要在curNode右边，注意在右边的话, k值要减去curNode.leftCount，因为在插入bst的过程中，我们已经知道有多少人比要插入node的人的高度高。

3.最后对bst做一个inorder traversal，得到最后结果

4.这种方法有机会将时间复杂度从O(n^2)降为O(nlogn),但由于树不能保证是balanced的，所以最坏情况还是O(n^2)

```java
class Solution {
    class TreeNode {
        int leftCount;
        int[] people;
        TreeNode left, right;

        public TreeNode(int[] people) {
            this.people = people;
            leftCount = 1;
            this.left = null;
            this.right = null;
        }
    }

    public int[][] reconstructQueue(int[][] people) {
        int[][] res = new int[people.length][2];

        if (people == null || people.length == 0) {
            return res;
        }

        Arrays.sort(people, new Comparator<int[]>(){
            @Override
            public int compare(int[] a, int[] b) {
                return a[0] == b[0] ? a[1] - b[1] : b[0] - a[0];
            }
        });

        TreeNode root = new TreeNode(people[0]);
        for (int i = 1; i < people.length; i++) {
            insert(root, new TreeNode(people[i]), people[i][1]);
        }

        inorderTraverse(root, res);
        return res;
    }

    public void insert(TreeNode root, TreeNode newNode, int k) {
        TreeNode curNode = root;

        while (curNode != null) {
            if (k < curNode.leftCount) {
                ++curNode.leftCount;
                if (curNode.left == null) {
                    curNode.left = newNode;
                    break;
                }
                else {
                    curNode = curNode.left;
                }
            }
            else {
                if (curNode.right == null) {
                    curNode.right = newNode;
                    break;
                }
                else {
                    k -= curNode.leftCount;
                    curNode = curNode.right;
                }
            }
        }
    }

    public void inorderTraverse(TreeNode root, int[][] res) {
        Stack<TreeNode> stack = new Stack();
        TreeNode curNode = root;
        int index = 0;

        while (curNode != null || !stack.isEmpty()) {
            if (curNode != null) {
                stack.push(curNode);
                curNode = curNode.left;
            }
            else {
                curNode = stack.pop();
                res[index] = curNode.people;
                ++index;
                curNode = curNode.right;
            }
        }
    }
}
```

## 3. Time & Space Complexity

**Sorting:** 时间复杂度O(nlogn + n^2) => O(n^2), 空间复杂度O(n), n为people数组的长度

**Binary Tree:** 时间复杂度：平均O(nlogn)，最坏O(n^2)， 空间复杂度O(n)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/algorithm-practice/leetcode/sort/406-queue-reconstruction-by-height.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.