当前位置: 面试刷题>> 栈集 (经典算法题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 示例代码

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 示例代码

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 示例代码

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

码小课:在码小课网站中,你可以找到更多关于算法和数据结构的详细讲解和实战练习,帮助你更深入地理解这些概念并提升编程能力。

推荐面试题