Esborra elements d'una pila que tenen per sota algú més gran que ells X12271

Implementeu una funció RECURSIVA que, donada una pila d’enters positius, retorna una pila amb els mateixos elements, excepte que s’han esborrat aquells elements que tenen per sota seu (no necessàrament inmediàtament) algun altre element estríctament més gran. Aquesta és la capcelera:

// Pre: s és una pila d'enters positius.
// Post: Retorna la pila resultant d'esborrar en s tots els elements per als quals podem
// trobar un altre element per sota seu que és estríctament més gran que ells.
stack<int> removeThoseWithBiggerUnder(stack<int> s);

Aquí tenim un exemple d’entrada i sortida de la funció, a on es mostren els elements de les piles des del fons de la pila a l’esquerra fins al top de la pila a la dreta:

5 4 1 8 9 7 9 9 8 4 2 5 10 3 9
=>
5 8 9 9 9 10

Observació Només cal enviar el procediment demanat; el programa principal serà ignorat.

Observació

La vostra funció i subfuncions que creeu han de treballar només amb piles. Heu de trobar una solució RECURSIVA i eficient del problema. Podeu crear funcions auxiliars per tal de millorar l’eficiència. En les crides recursives, incloeu la hipòtesi d’inducció, és a dir una explicació del que es cumpleix després de la crida, i també la funció de fita/decreixement o una justificació de perquè la funció recursiva acaba.

Una implementació no eficient que superi honestament els jocs de proves públics us permetrà obtenir una nota raonable, però per a superar tots els jocs de proves i obtenir la màxima nota haureu de pensar en una manera de fer-ho eficient.

Avaluació sobre 10 punts:

• Solució lenta: 6 punts.
• Solució lenta + justificació: 8 punts.
• solució ràpida: 8 punts.
• solució ràpida + justificació: 10 punts.