Concevoir une pile avec une opération d'incrémentation

1381. Concevoir une pile avec une opération d'incrémentation

Difficulté :Moyen

Sujets :Array, Stack, Design

Concevez une pile qui prend en charge les opérations d'incrémentation sur ses éléments.

Implémentez la classe CustomStack :

• CustomStack(int maxSize) Initialise l'objet avec maxSize qui est le nombre maximum d'éléments dans la pile.
• void push(int x) Ajoute x en haut de la pile si la pile n'a pas atteint la taille maximale.
• int pop() Pop et renvoie le haut de la pile ou -1 si la pile est vide.
• void inc(int k, int val) Incrémente les k éléments inférieurs de la pile de val. S'il y a moins de k éléments dans la pile, incrémentez tous les éléments de la pile.

Exemple 1 :

• Entrée :

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

• Sortie :

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

• Explication :

   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.

Contraintes :

• 1 <= maxSize, x, k <= 1000
• 0 <= val <= 100
• Au maximum 1 000 appels seront effectués vers chaque méthode d'incrémentation, push et pop séparément.

Indice :

1. Utilisez un tableau pour représenter la pile. Push ajoutera un nouvel entier au tableau. Pop supprime le dernier élément du tableau et l'incrément ajoutera val aux k premiers éléments du tableau.
2. Cette solution s'exécute en O(1) par push et pop et en O(k) par incrément.

Solution :

Nous pouvons suivre une implémentation typique de pile mais avec une méthode supplémentaire qui permet d'incrémenter les k éléments du bas d'une valeur donnée. L'opération d'incrémentation parcourra les k premiers éléments de la pile et ajoutera la valeur à chacun.

Nous implémenterons cette pile dans PHP 5.6, en utilisant un tableau pour représenter la pile. Les opérations principales sont :

1. push(x) : Ajoute l'élément x en haut de la pile, si la pile n'a pas atteint sa taille maximale.
2. pop() : supprime l'élément supérieur de la pile et le renvoie. Si la pile est vide, renvoie -1.
3. increment(k, val) : Ajoute la valeur val aux k premiers éléments de la pile, ou à tous les éléments si la pile contient moins de k éléments.

Implémentons cette solution en PHP : 1381. Concevoir une pile avec une opération d'incrémentation

<?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>
  
  
  Explication:
</h3>

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

<ul>
<li>Nous utilisons array_push pour ajouter des éléments à la pile. Nous vérifions si la taille actuelle de la pile est inférieure à maxSize. Si c'est le cas, on pousse le nouvel élément.</li>
</ul>
</li>
<li>
<p><strong>pop()</strong> :</p>

<ul>
<li>On vérifie si la pile est vide en utilisant empty($this->stack). S'il n'est pas vide, nous insérons l'élément supérieur en utilisant array_pop et le renvoyons. S'il est vide, on renvoie -1.</li>
</ul>
</li>
<li>
<p><strong>incrément($k, $val)</strong> :</p>

<ul>
<li>Nous calculons le minimum de k et la taille actuelle de la pile pour déterminer le nombre d'éléments à incrémenter. Nous parcourons ensuite ces éléments, en ajoutant val à chacun.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Exemple d'exécution :
</h3>

<p>Pour les opérations de saisie :<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],[],[],[],[]]

Le résultat sera :

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

Cette sortie est basée sur les éléments suivants :

• push(1) : La pile devient [1]
• push(2) : La pile devient [1, 2]
• pop() : renvoie 2, la pile devient [1]
• push(2) : La pile devient [1, 2]
• push(3) : La pile devient [1, 2, 3]
• push(4) : La pile reste [1, 2, 3] (maxSize atteinte)
• increment(5, 100) : La pile devient [101, 102, 103]
• increment(2, 100) : La pile devient [201, 202, 103]
• pop() : renvoie 103, la pile devient [201, 202]
• pop() : renvoie 202, la pile devient [201]
• pop() : renvoie 201, la pile devient []
• pop() : renvoie -1 (la pile est vide)

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!