Entwerfen Sie einen Stapel mit Inkrementoperation

1381. Entwerfen Sie einen Stapel mit Inkrementoperation

Schwierigkeit:Mittel

Themen:Array, Stack, Design

Entwerfen Sie einen Stapel, der Inkrementoperationen für seine Elemente unterstützt.

Implementieren Sie die CustomStack-Klasse:

• CustomStack(int maxSize) Initialisiert das Objekt mit maxSize, was der maximalen Anzahl von Elementen im Stapel entspricht.
• void push(int x) Fügt x oben zum Stapel hinzu, wenn der Stapel die maxSize nicht erreicht hat.
• int pop() Pops und gibt die Oberseite des Stapels zurück oder -1, wenn der Stapel leer ist.
• void inc(int k, int val) Erhöht die unteren k Elemente des Stapels um val. Wenn der Stapel weniger als k Elemente enthält, erhöhen Sie alle Elemente im Stapel.

Beispiel 1:

• Eingabe:

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

• Ausgabe:

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

• Erklärung:

   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.

Einschränkungen:

• 1 <= maxSize, x, k <= 1000
• 0 <= Wert <= 100
• Höchstens 1000 Aufrufe werden für jede Inkrementierungs-, Push- und Pop-Methode separat durchgeführt.

Hinweis:

1. Verwenden Sie ein Array, um den Stapel darzustellen. Push fügt dem Array eine neue Ganzzahl hinzu. Pop entfernt das letzte Element im Array und Inkrement fügt val zu den ersten k Elementen des Arrays hinzu.
2. Diese Lösung läuft in O(1) pro Push und Pop und O(k) pro Inkrement.

Lösung:

Wir können einer typischen Stack-Implementierung folgen, jedoch mit einer zusätzlichen Methode, die es ermöglicht, die unteren k Elemente um einen bestimmten Wert zu erhöhen. Die Inkrementierungsoperation durchläuft die ersten k Elemente des Stapels und fügt jedem den Wert hinzu.

Wir implementieren diesen Stack in PHP 5.6 und verwenden ein Array zur Darstellung des Stacks. Die Kernoperationen sind:

1. push(x): Fügt das Element x oben im Stapel hinzu, wenn der Stapel seine maximale Größe nicht erreicht hat.
2. pop(): Entfernt das oberste Element des Stapels und gibt es zurück. Wenn der Stapel leer ist, geben Sie -1 zurück.
3. inkrement(k, val): Fügt den Wert val zu den ersten k Elementen im Stapel hinzu oder zu allen Elementen, wenn der Stapel weniger als k Elemente enthält.

Lassen Sie uns diese Lösung in PHP implementieren: 1381. Entwerfen Sie einen Stapel mit Inkrementoperation

<?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
?>




<h3>
  
  
  Erläuterung:
</h3>

<ol>
<li>
<p><strong>push($x)</strong>:</p>

<ul>
<li>Wir verwenden array_push, um Elemente zum Stapel hinzuzufügen. Wir prüfen, ob die aktuelle Größe des Stapels kleiner als maxSize ist. Wenn ja, pushen wir das neue Element.</li>
</ul>
</li>
<li>
<p><strong>pop()</strong>:</p>

<ul>
<li>Wir prüfen, ob der Stapel leer ist, indem wir empty($this->stack) verwenden. Wenn es nicht leer ist, öffnen wir das oberste Element mit array_pop und geben es zurück. Wenn es leer ist, geben wir -1 zurück.</li>
</ul>
</li>
<li>
<p><strong>Inkrement($k, $val)</strong>:</p>

<ul>
<li>Wir berechnen das Minimum von k und die aktuelle Stapelgröße, um zu bestimmen, wie viele Elemente erhöht werden müssen. Anschließend durchlaufen wir diese Elemente und fügen jedem val hinzu.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Beispielausführung:
</h3>

<p>Für die Eingabeoperationen:<br>
</p>

<pre class="brush:php;toolbar:false">["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]

Die Ausgabe wird sein:

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

Diese Ausgabe basiert auf Folgendem:

• push(1): Stapel wird zu [1]
• push(2): Stapel wird zu [1, 2]
• pop(): Gibt 2 zurück, Stapel wird zu [1]
• push(2): Stapel wird zu [1, 2]
• push(3): Stapel wird zu [1, 2, 3]
• push(4): Stack bleibt [1, 2, 3] (maxSize erreicht)
• Inkrement(5, 100): Stapel wird zu [101, 102, 103]
• Inkrement(2, 100): Stapel wird zu [201, 202, 103]
• pop(): Gibt 103 zurück, Stapel wird zu [201, 202]
• pop(): Gibt 202 zurück, Stack wird zu [201]
• pop(): Gibt 201 zurück, Stapel wird zu []
• pop(): Gibt -1 zurück (Stapel ist leer)

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt vonEntwerfen Sie einen Stapel mit Inkrementoperation. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!