設計一個具有增量操作的堆疊

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中文網其他相關文章！