1172-餐盘栈

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 17:01:06 2023-09-13 17:01:06 Updated    

我们把无限数量 ∞ 的栈排成一行，按从左到右的次序从 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]

**解释：**
DinnerPlates D = DinnerPlates(2);  // 初始化，栈最大容量 capacity = 2
D.push(1);
D.push(2);
D.push(3);
D.push(4);
D.push(5);         // 栈的现状为：    2  4
                                    1  3  5
                                    ﹈ ﹈ ﹈
D.popAtStack(0);   // 返回 2。栈的现状为：      4
                                          1  3  5
                                          ﹈ ﹈ ﹈
D.push(20);        // 栈的现状为：  20  4
                                   1  3  5
                                   ﹈ ﹈ ﹈
D.push(21);        // 栈的现状为：  20  4 21
                                   1  3  5
                                   ﹈ ﹈ ﹈
D.popAtStack(0);   // 返回 20。栈的现状为：       4 21
                                            1  3  5
                                            ﹈ ﹈ ﹈
D.popAtStack(2);   // 返回 21。栈的现状为：       4
                                            1  3  5
                                            ﹈ ﹈ ﹈ 
D.pop()            // 返回 5。栈的现状为：        4
                                            1  3 
                                            ﹈ ﹈  
D.pop()            // 返回 4。栈的现状为：    1  3 
                                           ﹈ ﹈   
D.pop()            // 返回 3。栈的现状为：    1 
                                           ﹈   
D.pop()            // 返回 1。现在没有栈。
D.pop()            // 返回 -1。仍然没有栈。

提示：

  • 1 <= capacity <= 20000
  • 1 <= val <= 20000
  • 0 <= index <= 100000
  • 最多会对 push，pop，和 popAtStack 进行 200000 次调用。

方法一：数组 + 有序集合模拟

思路

用一个数组 stack 来模拟栈，编号为 index 的栈的顶部 stackTop 在数组中的下标 pos 可以通过公式来表示：pos} = \textit{index} \times \textit{capacity} + \textit{stackTop。用一个有序集合 poppedPos 来保存被方法 popAtStack 删除的位置。用数组 top 记录每个栈的栈顶元素在栈中的位置，比如 top}[1] = 2 就表示，编号为 1 的栈，栈顶元素在栈中的下标为 2（从 0 开始计数，capacity} > 2），即在这个栈中，它上面没有元素，它下面还有两个元素。

执行 push 时，先考虑 poppedPos 中的位置，如果非空，则找出最小的位置，把元素 push 到这个位置。如果为空，则往 stack 后追加，然后更新 top。

执行 popAtStack 时，先找出这个栈现在的栈顶位置，然后把这个位置的元素的下标计算出来并更新栈顶位置，把下标放入 poppedPos，返回元素的值。当然有可能这个栈是空的，此时要返回 -1。

执行 pop 时，情况比较复杂。直观的想法是，返回 stack 元素即可。但 stack 末尾元素可能早已被 popAtStack 删除，因此，应该返回处于 stack 末尾且不位于 popAtStack 中的位置，如果 stack 末尾位置出现在 popAtStack 中，直接把 stack 末尾元素删除，再进行重复判断，直到满足上述条件或者 stack 为空。找到符合条件的位置后，需要更新 top，然后返回元素的值。在执行 pop 时，上述判断可能会执行多次，但是一次 popAtStack 最多带来一次判断，因此不会带来时间复杂度的变大。

代码

[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class DinnerPlates {
    int capacity;
    List<Integer> stack;
    List<Integer> top;
    TreeSet<Integer> poppedPos;

    public DinnerPlates(int capacity) {
        this.capacity = capacity;
        stack = new LinkedList<>();
        top = new ArrayList<>();
        poppedPos = new TreeSet<>();
    }

    public void push(int val) {
        if (poppedPos.isEmpty()) {
            int pos = stack.size();
            stack.add(val);
            if (pos % capacity == 0) {
                top.add(0);
            }
            else {
                int stackPos = top.size()-1;
                int stackTop = top.get(stackPos);
                top.set(stackPos, stackTop + 1);
            }
        } else {
            int pos = poppedPos.pollFirst();
            stack.set(pos, val);
            int index = pos / capacity;
            int stackTop = top.get(index);
            top.set(index, stackTop + 1);
        }
    }

    public int pop() {
        while (!stack.isEmpty() && poppedPos.contains(stack.size()-1)) {
            stack.remove(stack.size()-1);
            int pos = poppedPos.pollLast();
            if (pos % capacity == 0) {
                top.remove(top.size()-1);
            }
        }
        if (stack.isEmpty()) {
            return -1;
        } else {
            int pos = stack.size() - 1;
            int val = stack.get(pos);
            stack.remove(pos);
            int index = top.size()-1;
            if (pos % capacity == 0) {
                top.remove(index);
            } else {
                top.set(index, index - 1);
            }
            return val;
        }
    }

    public int popAtStack(int index) {
        if (index >= top.size()) {
            return -1;
        }
        int stackTop = top.get(index);
        if (stackTop < 0) {
            return -1;
        }
        top.set(index, stackTop - 1);
        int pos = index * capacity + stackTop;
        poppedPos.add(pos);
        return stack.get(pos);
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class DinnerPlates {
public:
    DinnerPlates(int capacity) {
        this->capacity = capacity;
    }

    void push(int val) {
        if (poppedPos.empty()) {
            int pos = stk.size();
            stk.emplace_back(val);
            if (pos % capacity == 0) {
                top.emplace_back(0);
            } else {
                top.back()++;
            }
        } else {
            int pos = *poppedPos.begin();
            poppedPos.erase(pos);
            stk[pos] = val;
            int index = pos / capacity;
            top[index]++;
        }
    }
    
    int pop() {
        while (!stk.empty() && poppedPos.count(stk.size() - 1)) {
            stk.pop_back();
            int pos = *poppedPos.rbegin();
            poppedPos.erase(pos);
            if (pos % capacity == 0) {
                top.pop_back();
            }
        }
        if (stk.empty()) {
            return -1;
        } else {
            int pos = stk.size() - 1;
            int val = stk.back();
            stk.pop_back();
            if (pos % capacity == 0) {
                top.pop_back();
            } else {
                top.back() = top.size() - 2;
            }
            return val;
        }
    }
    
    int popAtStack(int index) {
        if (index >= top.size()) {
            return -1;
        }
        int stackTop = top[index];
        if (stackTop < 0) {
            return -1;
        }
        top[index]--;
        int pos = index * capacity + stackTop;
        poppedPos.emplace(pos);
        return stk[pos];
    }
private:
    int capacity;
    vector<int> stk;
    vector<int> top;
    set<int> poppedPos;
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
from sortedcontainers import *
class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.stack = []
        self.top = []
        self.poppedPos = SortedSet()

    def push(self, val: int) -> None:
        if not self.poppedPos:
            pos = len(self.stack)
            self.stack.append(val)
            if pos % self.capacity == 0:
                self.top.append(0)
            else:
                stackPos = len(self.top) - 1
                stackTop = self.top[stackPos]
                self.top[stackPos] = stackTop + 1
        else:
            pos = self.poppedPos.pop(0)
            self.stack[pos] = val
            index = pos // self.capacity
            stackTop = self.top[index]
            self.top[index] = stackTop + 1

    def pop(self) -> int:
        while self.stack and self.poppedPos and self.poppedPos[-1] == len(self.stack) - 1:
            self.stack.pop()
            pos = self.poppedPos.pop()
            if pos % self.capacity == 0:
                self.top.pop()
        if not self.stack:
            return -1
        else:
            pos = len(self.stack) - 1
            val = self.stack[pos]
            self.stack.pop()
            if pos % self.capacity == 0 and self.top:
                self.top.pop()
            elif self.top:
                self.top[-1] -= 1
            return val

    def popAtStack(self, index: int) -> int:
        if index >= len(self.top):
            return -1
        stackTop = self.top[index]
        if stackTop < 0:
            return -1
        self.top[index] = stackTop - 1
        pos = index * self.capacity + stackTop
        self.poppedPos.add(pos)
        return self.stack[pos]
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
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]
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
class TreeSet {
    constructor(comparator) {
        this.set = new Set();
        this.comparator = comparator || ((a, b) => a - b);
        this.array = [];
    }

    add(item) {
        if (!this.set.has(item)) {
            this.set.add(item);
            this.array.push(item);
            this.array.sort(this.comparator);
        }
    }

    delete(item) {
        if (this.set.has(item)) {
            this.set.delete(item);
            this.array.splice(this.array.indexOf(item), 1);
        }
    }

    has(item) {
        return this.set.has(item);
    }

    get size() {
        return this.set.size;
    }

    toArray() {
        return [...this.array];
    }

    pollFirst() {
        const item = this.array.shift();
        this.set.delete(item);
        return item;
    }

    pollLast() {
        const item = this.array.pop();
        this.set.delete(item);
        return item;
    }
}

var DinnerPlates = function(capacity) {
    this.capacity = capacity;
    this.stack = [];
    this.top = [];
    this.poppedPos = new TreeSet();
};

DinnerPlates.prototype.push = function(val) {
    if (this.poppedPos.size === 0) {
        const pos = this.stack.length;
        this.stack.push(val);
        if (pos % this.capacity === 0) {
            this.top.push(0);
        }
        else {
            const stackPos = this.top.length - 1;
            const stackTop = this.top[stackPos];
            this.top.splice(stackPos, 1 , stackTop + 1);
        }
    } else {
        const pos = this.poppedPos.pollFirst();
        this.stack.splice(pos, 1 , val);
        const index = Math.floor(pos / this.capacity);
        const stackTop = this.top[index];
        this.top.splice(index, 1 ,stackTop + 1);
    }
};

DinnerPlates.prototype.pop = function() {
    while (this.stack.length !== 0 && this.poppedPos.has(this.stack.length - 1)) {
        this.stack.splice(this.stack.length - 1,1);
        const pos = this.poppedPos.pollLast();
        if (pos % this.capacity === 0) {
            this.top.splice(this.top.length - 1, 1);
        }
    }
    if (this.stack.length === 0) {
        return -1;
    } else {
        const pos = this.stack.length - 1;
        const val = this.stack[pos];
        this.stack.splice(pos, 1);
        const index = this.top.length - 1;
        if (pos % this.capacity === 0) {
            this.top.splice(index, 1);
        } else {
            this.top.splice(index, 1 , index - 1);
        }
        return val;
    }
};

DinnerPlates.prototype.popAtStack = function(index) {
    if (index >= this.top.length) {
        return -1;
    }
    const stackTop = this.top[index];
    if (stackTop < 0) {
        return -1;
    }
    this.top.splice(index,  1, stackTop - 1);
    const pos = index * this.capacity + stackTop;
    this.poppedPos.add(pos);
    return this.stack[pos];
};

复杂度分析

  • 时间复杂度：记 n 为 push 的调用次数。单次 push 的时间复杂度为 O(\log n)，单次 popAtStack 的时间复杂度为 O(\log n)，pop 单次均摊的时间复杂度为 O(\log n)。

  • 空间复杂度：使用到的数组和有序集合空间复杂度均为 O(n)。

 Comments
On this page
1172-餐盘栈