设计一个具有增量操作的堆栈

1381。设计一个具有增量操作的堆栈

难度：中等

主题：数组、堆栈、设计

设计一个支持对其元素进行增量操作的堆栈。

实现 CustomStack 类：

• CustomStack(int maxSize) 使用 maxSize 初始化对象，maxSize 是堆栈中元素的最大数量。
• void push(int x) 如果堆栈尚未达到 maxSize，则将 x 添加到堆栈顶部。
• int pop() 弹出并返回堆栈顶部，如果堆栈为空，则返回-1。
• void inc(int k, int val) 将堆栈底部 k 个元素增加 val。如果堆栈中的元素少于 k 个，则将堆栈中的所有元素递增。

示例1：

• 输入：

  ["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
  [[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]

• 输出：

  [null,null,null,2,null,null,null,null,null,103,202,201,-1]

• 说明：

   CustomStack stk = new CustomStack(3); // Stack is Empty []
   stk.push(1);                          // stack becomes [1]
   stk.push(2);                          // stack becomes [1, 2]
   stk.pop();                            // return 2 --> Return top of the stack 2, stack becomes [1]
   stk.push(2);                          // stack becomes [1, 2]
   stk.push(3);                          // stack becomes [1, 2, 3]
   stk.push(4);                          // stack still [1, 2, 3], Do not add another elements as size is 4
   stk.increment(5, 100);                // stack becomes [101, 102, 103]
   stk.increment(2, 100);                // stack becomes [201, 202, 103]
   stk.pop();                            // return 103 --> Return top of the stack 103, stack becomes [201, 202]
   stk.pop();                            // return 202 --> Return top of the stack 202, stack becomes [201]
   stk.pop();                            // return 201 --> Return top of the stack 201, stack becomes []
   stk.pop();                            // return -1 --> Stack is empty return -1.

约束：

• 1
• 0
• 每个递增、压入和弹出方法最多分别调用 1000 次。

提示：

1. 使用数组来表示堆栈。 Push 会将新整数添加到数组中。 Pop 删除数组中的最后一个元素，increment 会将 val 添加到数组的前 k 个元素。
2. 此解决方案每次推送和弹出的运行时间为 O(1)，每次增量的运行时间为 O(k)。

解决方案：

我们可以遵循典型的堆栈实现，但使用额外的方法，允许将底部的 k 个元素增加给定值。增量操作将迭代堆栈的前 k 个元素并将值添加到每个元素。

我们将在 PHP 5.6 中实现这个堆栈，使用数组来表示堆栈。核心操作是：

1. push(x)：如果堆栈尚未达到其 maxSize，则将元素 x 添加到堆栈顶部。
2. pop()：移除栈顶元素并返回。如果堆栈为空，则返回-1。
3. increment(k, val)：将值 val 添加到堆栈中的前 k 个元素，如果堆栈包含的元素少于 k 个，则添加到所有元素。

让我们用 PHP 实现这个解决方案：1381。设计一个具有增量操作的堆栈

<?php
class CustomStack {
    /**
     * @var array
     */
    private $stack;
    /**
     * @var int
     */
    private $maxSize;
    /**
     * Constructor to initialize the stack with a given maxSize
     *
     * @param Integer $maxSize
     */
    function __construct($maxSize) {
        ...
        ...
        ...
        /**
         * go to ./solution.php
         */
    }

    /**
     * Push an element to the stack if it has not reached the maxSize
     *
     * @param Integer $x
     * @return NULL
     */
    function push($x) {
        ...
        ...
        ...
        /**
         * go to ./solution.php
         */
    }

    /**
     * Pop the top element from the stack and return it, return -1 if the stack is empty
     *
     * @return Integer
     */
    function pop() {
        ...
        ...
        ...
        /**
         * go to ./solution.php
         */
    }

    /**
     * Increment the bottom k elements of the stack by val
     *
     * @param Integer $k
     * @param Integer $val
     * @return NULL
     */
    function increment($k, $val) {
        ...
        ...
        ...
        /**
         * go to ./solution.php
         */
    }
}

/**
 * Your CustomStack object will be instantiated and called as such:
 * $obj = CustomStack($maxSize);
 * $obj->push($x);
 * $ret_2 = $obj->pop();
 * $obj->increment($k, $val);
 */

// Example usage
$customStack = new CustomStack(3);  // Stack is Empty []
$customStack->push(1);              // stack becomes [1]
$customStack->push(2);              // stack becomes [1, 2]
echo $customStack->pop() . "\n";    // return 2, stack becomes [1]
$customStack->push(2);              // stack becomes [1, 2]
$customStack->push(3);              // stack becomes [1, 2, 3]
$customStack->push(4);              // stack still [1, 2, 3], maxSize is 3
$customStack->increment(5, 100);    // stack becomes [101, 102, 103]
$customStack->increment(2, 100);    // stack becomes [201, 202, 103]
echo $customStack->pop() . "\n";    // return 103, stack becomes [201, 202]
echo $customStack->pop() . "\n";    // return 202, stack becomes [201]
echo $customStack->pop() . "\n";    // return 201, stack becomes []
echo $customStack->pop() . "\n";    // return -1, stack is empty
?>

解释：

1. 推($x):

   • 我们使用 array_push 将元素添加到堆栈中。我们检查堆栈的当前大小是否小于 maxSize。如果是，我们推送新元素。

2. pop():

   • 我们使用empty($this->stack)检查堆栈是否为空。如果它不为空，我们使用 array_pop 弹出顶部元素并返回它。如果为空，我们返回-1。

3. 增量($k, $val):

   • 我们计算 k 的最小值和当前堆栈大小来确定要增加多少个元素。然后我们循环这些元素，为每个元素添加 val。

执行示例：

对于输入操作：

["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]

输出将是：

[null, null, null, 2, null, null, null, null, null, 103, 202, 201, -1]

此输出基于以下内容：

• push(1)：堆栈变为 [1]
• push(2): 堆栈变成 [1, 2]
• pop()：返回2，栈变成[1]
• push(2): 堆栈变成 [1, 2]
• push(3): 堆栈变成 [1, 2, 3]
• push(4): 堆栈仍为 [1, 2, 3]（达到 maxSize）
• increment(5, 100)：堆栈变为 [101, 102, 103]
• increment(2, 100)：堆栈变为 [201, 202, 103]
• pop()：返回103，栈变成[201, 202]
• pop()：返回202，栈变成[201]
• pop()：返回201，栈变成[]
• pop()：返回-1（堆栈为空）

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是设计一个具有增量操作的堆栈的详细内容。更多信息请关注PHP中文网其他相关文章！