donné à deux séquences numériques uniques: Par exemple, le Order SO POP: 4 5 3 2 1 est légal et 4 3 5 1 2 n'est pas un ordre pop légal. Poussez l'ordre de pile et Ordre pop de pile , les numéros dans Poussez la commande sont en ordre de tri croissant, Demandez maintenant à la commande POP est légal ou non?
commande push est 1 2 3 4 5, SO 4 5 3 2 1 est un ordre pop légal, car nous pouvons pousser et faire la tête comme ceci:
poussez 1, poussez 2, poussez 3, poussez 4, pop, poussez 5, pop, pop, pop, pop
4 Réponses :
Étant donné que votre séquence push est en ordre croissant, alors lorsque vous voyez un numéro Par exemple, 4 3 5 1 2 n'est pas un ordre valide, car lorsque nous voyons "4" sauté, que tous les chiffres
plus petit que '4' mais pas encore éclairé auparavant doit être sauté en ordre décroissant. Cependant, la touche "1" d'abord puis "2" viole cette propriété. n dans votre file d'attente POP, puis
Tous les nombres qui sont 1) ci-dessous n et 2) non encore apparus, doivent être sautés en ordre décroissant.
Il semble que votre solution par maintien des chiffres maximum et minimum ne fonctionne pas pour la séquence 1, 2, 3, 5, 4 ..
Quelle est la complexité du temps? O (n ^ 2)?
@Dukeling: une vérification naïve serait O (n ^ 2), mais la vérification pourrait être effectuée dans O (n) avec une pile (un exemple serait votre solution: construisez une pile afin que vous puissiez savoir quel élément est déjà apparu ).
Exemple 1: {1, 2, 4, 3}, séquence juridique < Pré> xxx Exemple 2: {1, 4, 2, 3}, séquence illégale je suis Essayant de mon mieux pour expliquer mon idée, espérons que j'ai fait de l'évidence.
Vous simulez le push et POP commandez, je n'ai pas compris votre idée, désolé. Et il y a un petit bug dans votre code: vous ne pouvez pas utiliser pop () dans 'si' doit utiliser peek () ou autre méthode similaire.
@Hiway Désolé, je voulais modifier ma réponse mais je n'ai pas eu le temps. Maintenant, j'utilise des mots et des exemples pour expliquer mon idée. Vous pouvez vérifier cela maintenant :)
Une option consiste à construire réellement la pile:
pour chaque numéro Notez que cela n'exige pas que l'ordre push est ascendant. Vous pouvez profiter de la commande pour optimiser légèrement (à échouer plus tôt) en défaillant si < code> x est plus petit que le haut de la pile. Puisque vous ne poussez que chaque élément au plus une fois, ce qui précède est le temps linéaire (que vous ne pouvez pas faire mieux que) et linéaire Espace. Exemple: x dans l'ordre pop:
x . Si vous avez poussé tous les numéros et que vous n'avez pas trouvé x , il n'y a aucun moyen d'obtenir l'ordre pop.
x
Ceci peut être vérifié dans O (n) l'espace et o (1) espace en gardant une trace du maximum.
L'ordre push est en ordre croissant, ainsi que lorsque vous avez des éléments pop:
Donc il y a deux options:
4 5 3 2 1 est valide depuis 5> max (4), 3 <5, 2 <3 et 1 <2.
4 3 5 1 2 n'est pas valide depuis 2> 1 mais 2 1 2 3 5 4 est valide depuis 2> max (1), 3> max (2), 5> max (3) et 4 <5.
@ user2246674, ce n'est pas nécessaire, POP signifie d'obtenir et de retirer l'élément supérieur de la pile, nous ne pouvons pas spécifier de chiffrement à apparaître.
Ah, oui, qu'il y a n'importe quel de ces commandes ..
Quelle était ta question??
Cette question semble être hors sujets car il s'agit d'informatique, pas de programmes.
D'après ce que je peux comprendre, il semble être une tautologie. Que faut-il tester?
@bmargulies Il s'agit d'algorithmes. En disant que c'est "à propos de la science informatique" ne vous aide probablement pas vraiment trop pour quelqu'un qui ne sait pas sur le Science informatique site (si cela est ce que vous vouliez dire). Je crois que ces types de questions sont sur le sujet pour Engineering logiciel , ordinateur Science et Overflow de pile , mais Overflow de pile Certainement a le meilleur parti de ces types de questions (et je sais depuis ce type de questions préférées). Bien que je ne puisse pas vraiment discuter avec vous si vous vouliez dire que la question "doit démontrer une compréhension minimale du problème résolu".