La récupération de la Min élément dans une pile en O(1) Fois
La raison pour laquelle je te pose cette question c'est parce que je ne vois pas pourquoi la façon dont je pense ne peut pas être appliqué à cette question particulière
"Comment voulez-vous concevoir une pile, qui,
en plus de push et pop, a aussi une fonction min qui renvoie l'élément minimum? Push, pop et min devraient tous fonctionner en O(1) temps"
Ma solution de base: ne Serait-il pas possible si nous avions une variable dans pile de la classe, qu'à chaque fois que nous avancions d'un élément de pile nous allions vérifier si il est petit de la min variable. Si elle est d'assigner la valeur de la min, si ce n'est de les ignorer.
Vous obtenez toujours le O(1) comme la fonction min serait;
int getMinimum(){
return min;
}
Pourquoi cette solution n'est jamais mentionné, ou ce qui est la faute, avec la manière, je pense que?
- Que faire si l'élément minimum est sauté hors de la pile? Comment vous trouvez le nouveau minimum en O(1) fois?
- Merci beaucoup. Je l'ai maintenant
- double possible de la conception d'une pile tels que getMinimum( ) doit être O(1)
Vous devez vous connecter pour publier un commentaire.
Cela ne fonctionne pas si vous avez sauté des numéros hors de la pile.
Ex. 2,4,5,3,1. Après vous pop 1, quel est votre minimum?
La solution est de garder une pile de minimums, et pas seulement une valeur unique. Si vous rencontrez une valeur qui est la moins égal au minimum actuel, vous avez besoin de la pousser sur le min de la pile.
Ex.
Utiliser une liste chaînée de garder une trace de la valeur minimale qui va être à la tête.
Noter que linkedlist.app= append ( nous mettre la valeur dans la queue ).
linkedlist.pre =prepend ( nous mettre la valeur en tant que chef de la linkedlist)
public class Pile {
}
J'ai trouvé cette solution ici
Nous définissons une variable minEle qui stocke le minimum actuel de l'élément dans la pile. Maintenant la partie intéressante est, comment gérer le cas lors de l'élément minimum est supprimé. Pour gérer cela, nous appuyer sur “2x – minEle” dans la pile au lieu de x, de sorte que le minimum de l'élément peuvent être récupérées à l'aide de courant minEle et sa valeur stockée dans la pile. Ci-dessous sont les étapes détaillées et l'explication de travail.
Push(x) : Insère x en haut de la pile.
Pop() : Supprime un élément à partir du haut de la pile.
Comment cette approche de travail?
Lors de l'élément à insérer est moins de minEle, nous insérer “2x – minEle”.
La chose importante à la prise de notes est, 2x – minEle sera toujours inférieur à x (preuve ci-dessous), c'est à dire, la nouvelle minEle et tout en sautant hors cet élément, nous allons voir que quelque chose d'inhabituel s'est passé comme le sauté élément est inférieure à la minEle. Nous allons donc être mise à jour minEle
Comment 2*x - minEle est inférieur à x en push()?
x < minEle qui signifie que x - minEle < 0
//Ajout de x sur les deux côtés
x - minEle + x < 0 + x
2*x - minEle < x
Nous pouvons conclure 2*x - minEle < nouvelle minEle
Tout popping out, si nous trouvons l'élément(y) de moins que l'actuel minEle, nous constatons que la nouvelle minEle = 2*minEle – y.
Comment précédentes élément minimum, prevMinEle est, 2*minEle - y?
pop() est y éclatés élément?
//Nous avons repoussé y 2x - prevMinEle. Ici
//prevMinEle est minEle avant de y a été inséré
y = 2*x - prevMinEle
//Valeur de minEle a été faite égale à x
minEle = x .
nouveau minEle = 2 * minEle - y