2024-03-09：用go语言，我们把无限数量的栈排成一行，按从左到右的次序从 0 开始编号， 每个栈的的最大容量 capac

2024-03-09：用go语言，我们把无限数量的栈排成一行，按从左到右的次序从 0 开始编号，

每个栈的的最大容量 capacity 都相同。实现一个叫「餐盘」的类 DinnerPlates，

DinnerPlates(int capacity) - 给出栈的最大容量 capacity，

void push(int val) 将给出的正整数 val 推入 从左往右第一个 没有满的栈，

int pop() 返回 从右往左第一个 非空栈顶部的值，并将其从栈中删除，

如果所有的栈都是空的，请返回 -1。

int popAtStack(int index) - 返回编号 index 的栈顶部的值，并将其从栈中删除，

如果编号 index 的栈是空的，请返回 -1。

输入：["DinnerPlates","push","push","push","push","push","popAtStack","push","push","popAtStack","popAtStack","pop","pop","pop","pop","pop"][[2],[1],[2],[3],[4],[5],[0],[20],[21],[0],[2],[],[],[],[],[]]。

输出：[null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]。

答案2024-03-09：

来自左程云。

灵捷3.5

大体步骤如下：

这个问题需要实现一个类DinnerPlates，其中含有Constructor、Push、Pop和PopAtStack四个方法。这个类可以理解成是具有固定容量的多个栈构成的一种数据结构。根据题目描述和提供的 Go 代码文件，这里来分步骤描述大体过程，然后讨论总的时间复杂度和总的空间复杂度。

1.Constructor:

• 当创建DinnerPlates实例时，通过调用Constructor方法初始化一个 DinnerPlates 类型的实例。需要传入一个参数capacity表示栈的最大容量。在这个方法中，将capacity存储到实例字段中，并初始化stack、top和poppedPos三个切片。

2.Push:

• 当调用Push方法时，将给定的整数值val推入从左到右第一个没有满的栈。

• 如果所有栈都已满，应该创建一个新的栈来存储val。

• 如果有栈未满，则将val推入最左侧未满的栈中，并更新top数组和stack数组。

3.Pop:

• 当调用Pop方法时，应该返回最右侧非空栈顶的值，并将其从栈中删除。如果所有的栈都为空，返回 -1。

• 如果有非空的栈，应该找到最右侧非空栈并返回它的栈顶的值，然后将其值从栈中删除。

4.PopAtStack:

• 当调用PopAtStack方法时，应该返回指定index栈的栈顶的值，并将其从栈中删除。如果指定index的栈为空，返回 -1。

• 需要更新top数组和poppedPos数组，以确保栈的一致性。

总的时间复杂度：

• Push 方法的时间复杂度为 O(1)。

• Pop 方法的时间复杂度为 O(1)。

• PopAtStack 方法的时间复杂度为 O(log n)，其中 n 是被删除的元素的数量。

总的空间复杂度：

• 需要 O(n) 的空间来存储栈中的所有元素，其中 n 是所有栈的元素数量。

go完整代码如下：

package main

import (

"fmt"

"sort"

)

type DinnerPlates struct {

capacity  int

stack     []int

top       []int

poppedPos []int

}

func Constructor(capacity int) DinnerPlates {

return DinnerPlates{capacity, []int{}, []int{}, []int{}}

}

func (this *DinnerPlates) Push(val int) {

if len(this.poppedPos) == 0 {

pos := len(this.stack)

this.stack = append(this.stack, val)

if pos%this.capacity == 0 {

this.top = append(this.top, 0)

} else {

stackPos := len(this.top) - 1

stackTop := this.top[stackPos]

this.top[stackPos] = stackTop + 1

}

} else {

pos := this.poppedPos[0]

this.poppedPos = this.poppedPos[1:]

this.stack[pos] = val

index := pos / this.capacity

stackTop := this.top[index]

this.top[index] = stackTop + 1

}

}

func (this *DinnerPlates) Pop() int {

for len(this.stack) > 0 && len(this.poppedPos) > 0 && this.poppedPos[len(this.poppedPos)-1] == len(this.stack)-1 {

this.stack = this.stack[:len(this.stack)-1]

pos := this.poppedPos[len(this.poppedPos)-1]

this.poppedPos = this.poppedPos[:len(this.poppedPos)-1]

if pos%this.capacity == 0 {

this.top = this.top[:len(this.top)-1]

}

}

if len(this.stack) == 0 {

return -1

} else {

pos := len(this.stack) - 1

val := this.stack[pos]

this.stack = this.stack[:pos]

if pos%this.capacity == 0 && len(this.top) > 0 {

this.top = this.top[:len(this.top)-1]

} else if len(this.top) > 0 {

this.top[len(this.top)-1] -= 1

}

return val

}

}

func (this *DinnerPlates) PopAtStack(index int) int {

if index >= len(this.top) {

return -1

}

stackTop := this.top[index]

if stackTop < 0 {

return -1

}

this.top[index] = stackTop - 1

pos := index*this.capacity + stackTop

i := sort.SearchInts(this.poppedPos, pos)

this.poppedPos = append(this.poppedPos, 0)

copy(this.poppedPos[i+1:], this.poppedPos[i:])

this.poppedPos[i] = pos

return this.stack[pos]

}

func main() {

dinnerPlates := Constructor(2)

dinnerPlates.Push(1)

dinnerPlates.Push(2)

dinnerPlates.Push(3)

dinnerPlates.Push(4)

dinnerPlates.Push(5)

fmt.Println(dinnerPlates.PopAtStack(0))

dinnerPlates.Push(20)

dinnerPlates.Push(21)

fmt.Println(dinnerPlates.PopAtStack(0))

fmt.Println(dinnerPlates.PopAtStack(2))

fmt.Println(dinnerPlates.Pop())

fmt.Println(dinnerPlates.Pop())

fmt.Println(dinnerPlates.Pop())

fmt.Println(dinnerPlates.Pop())

fmt.Println(dinnerPlates.Pop())

}

在这里插入图片描述