2021-12-14：根据身高重建队列。
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
力扣406。
答案2021-12-14：
具体见代码。golang代码有点问题，具体可查看java代码。
代码用golang编写。代码如下：
package main
import (
"fmt"
"sort"
)
func main() {
people := [][]int{{6, 0}, {5, 0}, {4, 0}, {3, 2}, {2, 2}, {1, 4}}
ret := reconstructQueue2(people)
fmt.Println(ret)
}
func reconstructQueue1(people [][]int) [][]int {
N := len(people)
units := make([]*Unit, N)
for i := 0; i < N; i++ {
units[i] = NewUnit(people[i][0], people[i][1])
}
sort.Slice(units, func(i, j int) bool {
o1 := units[i]
o2 := units[j]
if o1.h != o2.h {
return o2.h < o1.h
} else {
return o1.k > o2.k
}
})
arrList := make([]*Unit, 0)
for _, unit := range units {
arrListCopy := arrList[0:unit.k]
arrListCopy = append(arrListCopy, unit)
arrListCopy = append(arrListCopy, arrList[unit.k:]...)
arrList = arrListCopy
}
ans := make([][]int, N)
for i := 0; i < N; i++ {
ans[i] = make([]int, 2)
}
index := 0
for _, unit := range arrList {
ans[index][0] = unit.h
ans[index][1] = unit.k
index++
}
return ans
}
func reconstructQueue2(people [][]int) [][]int {
N := len(people)
units := make([]*Unit, N)
for i := 0; i < N; i++ {
units[i] = NewUnit(people[i][0], people[i][1])
}
sort.Slice(units, func(i, j int) bool {
o1 := units[i]
o2 := units[j]
if o1.h != o2.h {
return o2.h < o1.h
} else {
return o1.k > o2.k
}
})
tree := &SBTree{}
for i := 0; i < N; i++ {
tree.insert(units[i].k, i)
}
allIndexes := tree.allIndexes()
ans := make([][]int, N)
for i := 0; i < N; i++ {
ans[i] = make([]int, 2)
}
index := 0
for _, arri := range *allIndexes {
ans[index][0] = units[arri].h
ans[index][1] = units[arri].k
index++
}
return ans
}
type Unit struct {
h int
k int
}
func NewUnit(height, greater int) *Unit {
ret := &Unit{}
ret.h = height
ret.k = greater
return ret
}
type SBTNode struct {
value int
l *SBTNode
r *SBTNode
size int
}
func NewSBTNode(arrIndex int) *SBTNode {
ret := &SBTNode{}
ret.value = arrIndex
ret.size = 1
return ret
}
func twoSelectOne(c bool, a, b int) int {
if c {
return a
} else {
return b
}
}
type SBTree struct {
root *SBTNode
}
func (this *SBTree) rightRotate(cur *SBTNode) *SBTNode {
leftNode := cur.l
cur.l = leftNode.r
leftNode.r = cur
leftNode.size = cur.size
a := 0
if cur.l != nil {
a = cur.l.size
}
b := 0
if cur.r != nil {
b = cur.r.size
}
cur.size = a + b + 1
return leftNode
}
func (this *SBTree) leftRotate(cur *SBTNode) *SBTNode {
rightNode := cur.r
cur.r = rightNode.l
rightNode.l = cur
rightNode.size = cur.size
cur.size = (twoSelectOne(cur.l != nil, cur.l.size, 0)) + (twoSelectOne(cur.r != nil, cur.r.size, 0)) + 1
return rightNode
}
func (this *SBTree) maintain(cur *SBTNode) *SBTNode {
if cur == nil {
return nil
}
leftSize := 0
if cur.l != nil {
leftSize = cur.l.size
}
leftLeftSize := 0
if cur.l != nil && cur.l.l != nil {
leftLeftSize = cur.l.l.size
} else {
leftLeftSize = 0
}
leftRightSize := 0
if cur.l != nil && cur.l.r != nil {
leftRightSize = cur.l.r.size
}
rightSize := 0
if cur.r != nil {
rightSize = cur.r.size
}
rightLeftSize := 0
if cur.r != nil && cur.r.l != nil {
rightLeftSize = cur.r.l.size
}
rightRightSize := 0
if cur.r != nil && cur.r.r != nil {
rightRightSize = cur.r.r.size
}
if leftLeftSize > rightSize {
cur = this.rightRotate(cur)
cur.r = this.maintain(cur.r)
cur = this.maintain(cur)
} else if leftRightSize > rightSize {
cur.l = this.leftRotate(cur.l)
cur = this.rightRotate(cur)
cur.l = this.maintain(cur.l)
cur.r = this.maintain(cur.r)
cur = this.maintain(cur)
} else if rightRightSize > leftSize {
cur = this.leftRotate(cur)
cur.l = this.maintain(cur.l)
cur = this.maintain(cur)
} else if rightLeftSize > leftSize {
cur.r = this.rightRotate(cur.r)
cur = this.leftRotate(cur)
cur.l = this.maintain(cur.l)
cur.r = this.maintain(cur.r)
cur = this.maintain(cur)
}
return cur
}
func (this *SBTree) insert0(root *SBTNode, index int, cur *SBTNode) *SBTNode {
if root == nil {
return cur
}
root.size++
leftAndHeadSize := 0
if root.l != nil {
leftAndHeadSize = root.l.size + 1
} else {
leftAndHeadSize = 1
}
if index < leftAndHeadSize {
root.l = this.insert0(root.l, index, cur)
} else {
root.r = this.insert0(root.r, index-leftAndHeadSize, cur)
}
root = this.maintain(root)
return root
}
func (this *SBTree) get0(root *SBTNode, index int) *SBTNode {
leftSize := twoSelectOne(root.l != nil, root.l.size, 0)
if index < leftSize {
return this.get0(root.l, index)
} else if index == leftSize {
return root
} else {
return this.get0(root.r, index-leftSize-1)
}
}
func (this *SBTree) process(head *SBTNode, indexes *[]int) {
if head == nil {
return
}
this.process(head.l, indexes)
//indexes.addLast(head.value)
*indexes = append(*indexes, head.value)
this.process(head.r, indexes)
}
func (this *SBTree) insert(index, value int) {
cur := NewSBTNode(value)
if this.root == nil {
this.root = cur
} else {
if index <= this.root.size {
this.root = this.insert0(this.root, index, cur)
}
}
}
func (this *SBTree) get(index int) int {
ans := this.get0(this.root, index)
return ans.value
}
func (this *SBTree) allIndexes() *[]int {
//LinkedList<Integer> indexes = new LinkedList<>();
indexes := make([]int, 0)
this.process(this.root, &indexes)
return &indexes
} 执行结果如下：
***
[左神java代码](
