インクリメント操作を使用したスタックの設計

1381。インクリメント操作を使用したスタックの設計

難易度: 中

トピック: 配列、スタック、デザイン

要素のインクリメント操作をサポートするスタックを設計します。

CustomStack クラスを実装します:

• CustomStack(int 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. 配列を使用してスタックを表します。プッシュすると、新しい整数が配列に追加されます。 Pop は配列の最後の要素を削除し、increment は配列の最初の k 要素に val を追加します。
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. push($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 で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上がインクリメント操作を使用したスタックの設計の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。