当前位置： 面试刷题>> 栈集 (经典算法题500道)
**题目描述补充**：
设计一个栈的集合（StackSet），该集合支持以下操作：
1. **Push(int value, int stackId)**: 将一个整数`value`压入指定编号的栈`stackId`中。如果栈不存在，则创建一个新的栈。
2. **Pop(int stackId)**: 弹出指定编号的栈`stackId`的栈顶元素。如果栈为空或不存在，则不执行任何操作。
3. **Increment(int k, int val)**: 对栈中前`k`个非空栈的栈顶元素执行加`val`操作。如果栈的个数少于`k`，则对前`n`个栈（`n`为栈的个数）的栈顶元素执行加`val`操作。
4. **getMax(int stackId)**: 返回指定编号的栈`stackId`的栈顶元素（如果栈不为空）。如果栈为空或不存在，则返回-1。
**注意**：栈的数量和栈中的元素数量可能会非常大，因此需要考虑算法的空间和时间效率。
### PHP 示例代码
```php
class Stack {
private $elements;
public function __construct() {
$this->elements = [];
}
public function push($value) {
$this->elements[] = $value;
}
public function pop() {
if (!empty($this->elements)) {
return array_pop($this->elements);
}
return null;
}
public function top() {
return empty($this->elements) ? null : end($this->elements);
}
}
class StackSet {
private $stacks;
public function __construct() {
$this->stacks = [];
}
public function push($value, $stackId) {
if (!isset($this->stacks[$stackId])) {
$this->stacks[$stackId] = new Stack();
}
$this->stacks[$stackId]->push($value);
}
public function pop($stackId) {
if (isset($this->stacks[$stackId])) {
$this->stacks[$stackId]->pop();
}
}
public function increment($k, $val) {
$stackCount = count($this->stacks);
$maxStacks = min($k, $stackCount);
for ($i = 0; $i < $maxStacks; $i++) {
if (!empty($this->stacks[$i]->elements)) {
$top = &$this->stacks[$i]->elements[count($this->stacks[$i]->elements) - 1];
$top += $val;
}
}
}
public function getMax($stackId) {
if (isset($this->stacks[$stackId]) && !empty($this->stacks[$stackId]->elements)) {
return end($this->stacks[$stackId]->elements);
}
return -1;
}
}
// 示例使用
$stackSet = new StackSet();
$stackSet->push(1, 0);
$stackSet->push(2, 0);
$stackSet->push(2, 1);
$stackSet->push(2, 1);
$stackSet->increment(2, 5);
echo $stackSet->getMax(0); // 输出 6
echo $stackSet->getMax(1); // 输出 7
```
### Python 示例代码
```python
class Stack:
def __init__(self):
self.elements = []
def push(self, value):
self.elements.append(value)
def pop(self):
if self.elements:
return self.elements.pop()
def top(self):
if self.elements:
return self.elements[-1]
class StackSet:
def __init__(self):
self.stacks = {}
def push(self, value, stackId):
if stackId not in self.stacks:
self.stacks[stackId] = Stack()
self.stacks[stackId].push(value)
def pop(self, stackId):
if stackId in self.stacks:
self.stacks[stackId].pop()
def increment(self, k, val):
for i in range(min(k, len(self.stacks))):
if self.stacks[i].elements:
self.stacks[i].elements[-1] += val
def getMax(self, stackId):
if stackId in self.stacks and self.stacks[stackId].elements:
return self.stacks[stackId].elements[-1]
return -1
# 示例使用
stack_set = StackSet()
stack_set.push(1, 0)
stack_set.push(2, 0)
stack_set.push(2, 1)
stack_set.push(2, 1)
stack_set.increment(2, 5)
print(stack_set.getMax(0)) # 输出 6
print(stack_set.getMax(1)) # 输出 7
```
### JavaScript 示例代码
```javascript
class Stack {
constructor() {
this.elements = [];
}
push(value) {
this.elements.push(value);
}
pop() {
if (this.elements.length > 0) {
return this.elements.pop();
}
}
top() {
if (this.elements.length > 0) {
return this.elements[this.elements.length - 1];
}
return null;
}
}
class StackSet {
constructor() {
this.stacks = {};
}
push(value, stackId) {
if (!this.stacks[stackId]) {
this.stacks[stackId] = new Stack();
}
this.stacks[stackId].push(value);
}
pop(stackId) {
if (this.stacks[stackId]) {
this.stacks[stackId].pop();
}
}
increment(k, val) {
const stackKeys = Object.keys(this.stacks);
for (let i = 0; i < Math.min(k, stackKeys.length); i++) {
const stack = this.stacks[parseInt(stackKeys[i])];
if (stack.elements.length > 0) {
stack.elements[stack.elements.length - 1] += val;
}
}
}
getMax(stackId) {
if (this.stacks[stackId] && this.stacks[stackId].elements.length > 0) {
return this.stacks[stackId].elements[this.stacks[stackId].elements.length - 1];
}
return -1;
}
}
// 示例使用
const stackSet = new StackSet();
stackSet.push(1, 0);
stackSet.push(2, 0);
stackSet.push(2, 1);
stackSet.push(2, 1);
stackSet.increment(2, 5);
console.log(stackSet.getMax(0)); // 输出 6
console.log(stackSet.getMax(1)); // 输出 7
```
**码小课**：在码小课网站中，你可以找到更多关于算法和数据结构的详细讲解和实战练习，帮助你更深入地理解这些概念并提升编程能力。