-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDinnerPlateStacks.js
More file actions
96 lines (86 loc) · 2.71 KB
/
Copy pathDinnerPlateStacks.js
File metadata and controls
96 lines (86 loc) · 2.71 KB
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
// https://leetcode-cn.com/problems/dinner-plate-stacks/
var Test = require('../Common/Test');
var DinnerPlates = function (capacity) {
this.capacity = capacity;
this.stacks = [];
this.indexes = [];
};
DinnerPlates.prototype.push = function (val) {
if (this.indexes.length > 0) {
const index = this.indexes[0];
const stack = this.stacks[index];
stack.push(val);
if (stack.length == this.capacity) {
this.indexes.shift();
}
}
else {
if (this.capacity > 1) {
this.indexes.push(this.stacks.length);
}
this.stacks.push([val]);
}
};
DinnerPlates.prototype.pop = function () {
let lastStack;
while (this.stacks.length > 0) {
const stack = this.stacks[this.stacks.length - 1];
if (stack.length > 0) {
lastStack = stack;
break;
}
else {
this.stacks.pop();
this.indexes.pop();
}
}
if (lastStack) {
if (lastStack.length == this.capacity) {
// this.insertIndex(this.stacks.length - 1);
this.indexes.push(this.stacks.length - 1);
}
return lastStack.pop();
}
else {
return -1;
}
};
DinnerPlates.prototype.popAtStack = function (index) {
const stack = this.stacks[index];
if (!stack || stack.length == 0) {
return -1;
}
else {
if (stack.length == this.capacity) {
this.insertIndex(index);
}
return stack.pop();
}
};
DinnerPlates.prototype.insertIndex = function (index) {
const i = this.indexes.findIndex(i => index < i);
if (i != -1) {
this.indexes.splice(i, 0, index);
}
else {
this.indexes.push(index);
}
}
/**
* Your DinnerPlates object will be instantiated and called as such:
* var obj = new DinnerPlates(capacity)
* obj.push(val)
* var param_2 = obj.pop()
* var param_3 = obj.popAtStack(index)
*/
function test(ops, params) {
Test.testWithInstructions(DinnerPlates, ops, params);
}
// test(["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], [], [], [], [], []]);
test(["DinnerPlates", "push", "push", "push", "popAtStack", "pop", "pop"],
[[1], [1], [2], [3], [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], [], [], [], [], []]
["DinnerPlates", "push", "push", "push", "popAtStack", "pop", "pop"]
[[1], [1], [2], [3], [1], [], []]