Następny Największy Element

Zadanie

Dana jest tablica liczb całkowitych na której elementy nie są w żaden sposób uporządkowane. Napisz program, który dla każdego elementu wyznaczy element większy w dalszej części tablicy niż on sam. Jeśli nie istnieje wypisz -1.

Przykład

Przykładowo jest dana tablica liczb [5, 4, 10, 2, 7, 1]. Wynikiem działania algorytmu powinna być tablica [10, 10, -1, 7, -1, -1]. Wynika to z faktu, że największy element po 5 to 10. Podobnie dla liczby 4. Z kolei 10 nie ma większej wartości występującej po niej, więc oznaczamy to wartością -1. Te same zasady dotyczą ostatnich trzech liczb, ale tylko 2 ma większą liczbę na prawo i jest to 7.

Implementacja

Rozwiązanie Proste

Zadanie można rozwiązać algorytmem, który dla każdego elementu listy przejrzy elementy w dalszej części. Oto przykłoadyw kod realizujący to:

1. def NastepnyWiekszy(dane):
2.   wynik = [0 for x in dane]
3.   for i in range(len(dane)):
4.     max = -1
5.     for j in range(i, len(dane)):
6.       if dane[i] < dane[j]:
7.         max = dane[j]
8.         break
9.     wynik[i] = max
10.   return wynik

Rozwiązanie składa się z dwóch pętli. Najgorszym przypadkiem jest tablica liczb w kolejności malejącej - wtedy dla i-tego elementu trzeba sprawdzić n - i - 1 dalszych liczb. Jest to złożoność identyczna z sortowaniem bąbelkowym, a więc złożoność algorytmu jest kwadratowa O(n²).

Implementacja

Rozwiązanie Optymalne

Poprzedni algorytm można usprawnić. Można to zrobić poprzez optymalizację procesu wyszukiwania. Otóż należy utworzyć dodatkową kolejkę w której będą przechowywane jeszcze nie opisane liczby. Bardzo ważne jest to, aby kolejka ta była automatycznie sortowana po wartościach elementu, a więc trzeba pamiętać parę wartość x indeks, aby później można się było odwołać do odpowiedniej pozycji. Jeśli kolejka nie jest pusta to sprawdzamy czy aktualny element jest większy od jakiegokolwiek w kolejce. Jeśli tak to należy wpisać aktualny element jako element od nich większy.

Oto przykładowy kod:

1. def NastepnyWiekszy(dane):
2.   wynik = [0 for x in dane]
3.   kolejka = []
4.   for i in range(len(dane)):
5.     while len(kolejka) != 0:
6.       el = kolejka[0]
7.       if el[0] < dane[i]:
8.         wynik[el[1]] = dane[i]
9.         kolejka.pop(0)
10.       else:
11.         break
12.     kolejka.append((dane[i], i))
13.     kolejka.sort()
14.   while len(kolejka) != 0:
15.     el = kolejka.pop(0)
16.     wynik[el[1]] = -1
17.   return wynik

Przyjmując, że tablica składa się z n elementów, a wstawienie elementu do kolejki jest log₂n to ostateczna złożoność algorytmu wynosi O(nlog₂n) co jest znacząco szybsze od złożoności kwadratowej.

Testowanie funkcji

Wybrane rozwiązanie można przetestować poprzez przykładowy kod poniżej, który wczyta tablicę, a następnie wypisze wynik.

1. print("Podaj liczb(y):")
2. dane = [int(x) for x in input().split()]
3. wynik = NastepnyWiekszy(dane)
4. for i in range(len(dane)):
5.   print(dane[i], "\t>", wynik[i])

• Kod źródłowy Implementacja