根据身高重建队列

1. 题目描述

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

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

2. 思路

1. 思路一
   • 先排序，再插队
   • 对于数组（a, b），先根据a降序排序，然后根据b升序排序

3. 实现

3.1. 排序

func reconstructQueue(people [][]int) [][]int {
    //按照身高顺序逆序排序
    sort.Slice(people, func(i, j int) bool {
        a := people[i]
        b := people[j]
        return a[0] > b[0] || a[0] == b[0] && a[1] < b[1]
    })

    res := make([][]int, 0)
    for _, person := range people {
        res = insert(res, person[1], person)
    }
    return res

}

// 插入元素到slice的第index个位置
func insert(people [][]int, index int, person []int) [][]int {
    current := [][]int{person}
    left := people[:index]
    right := people[index:]

    res := append(current, right...)
    res = append(left, res...)
    return res
}

4. 参考

• 【先排序，再插队】动画演示算法过程，有点小套路 - 根据身高重建队列 - 力扣（LeetCode）