1884 - UEMM1

Cerința

Se dă un șir cu n elemente, numere naturale. Să se afișeze, pentru fiecare element din șir, valoarea din șir aflată după acesta și mai mare decât acesta (Următorul Element Mai Mare). Dacă o asemenea valoare nu există, se va afișa -1.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi cele n elemente ale șirului.

Date de ieșire

Programul va afișa pe ecran cele n valori determinate, separate prin câte un spațiu.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• elementele șirului vor fi mai mai mici decât 1.000.000

Exemplu:

Intrare

5

3 4 3 5 1

Ieșire

4 5 5 -1 -1

Rezolvare

<syntaxhighlight lang="python" line="1" start="1">

def urmatorul_element_mai_mare(n, sir):

   # Inițializăm rezultatul cu -1 pentru toate elementele
   rezultat = [-1] * n
   # Inițializăm o stivă goală pentru a păstra indicii elementelor
   stiva = []

   # Parcurgem fiecare element din șir
   for i in range(n):
       # Cât timp stiva nu este goală și elementul curent este mai mare decât elementul din vârful stivei
       while stiva and sir[stiva[-1]] < sir[i]:
           # Actualizăm rezultatul pentru indicele din vârful stivei cu valoarea actuală din șir
           rezultat[stiva.pop()] = sir[i]
       # Adăugăm indicele elementului curent în stivă
       stiva.append(i)

   # Returnăm rezultatul
   return rezultat

1. Citim numărul de elemente

n = int(input("Introduceți numărul de elemente: "))

1. Citim șirul de numere

sir = list(map(int, input("Introduceți elementele șirului, separate prin spațiu: ").split()))

1. Apelăm funcția și afișăm rezultatul

print(urmatorul_element_mai_mare(n, sir))

</syntaxhighlight>