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

Exemplul 1:

Intrare

5
3 4 3 5 1

Ieșire

Datele de intrare corespund restrictiilor impuse.
4 5 5 -1 -1

Exemplul 2:

Intrare

UEMM1

Ieșire

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

def verificare_restrictii(numere):    # functia de verificare a datelor de intrare
    if 1 <= numere <= 100000:
        return True
    else:
        return False


def urmatorul_element_mai_mare(numere, string):
    # Inițializăm rezultatul cu -1 pentru toate elementele
    rezultat = [-1] * numere
    # Inițializăm o stivă goală pentru a păstra indicii elementelor
    stiva = []

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

    # Returnăm rezultatul
    return rezultat


if __name__ == '__main__':
    try:
        # Citim numărul de elemente
        n = int(input("Introduceți numărul de elemente: "))
        # Citim șirul de numere
        sir = list(map(int, input("Introduceți elementele șirului, separate prin spațiu: ").split()))

        if verificare_restrictii(n):             # verificam datele de intrare
            print("Datele de intrare corespund restrictiilor impuse.")
            # Apelăm funcția și afișăm rezultatul
            print(urmatorul_element_mai_mare(n, sir))
        else:
            print("Datele de intrare nu corespund restrictiilor impuse.")
    # ne asteptam la 2 tipuri de erori din cauza datelor de intrare, le tratam corespunzator
    except ValueError:
        print("Datele de intrare nu corespund restrictiilor impuse.")
    except IndexError:
        print("Datele de intrare nu corespund restrictiilor impuse.")