Policz Wieżowce

Zadanie

Dana jest lista wysokości kolejnych wieżowców znajdujących się na wprost patrzącego. Sprawdź ile z nich jest tak naprawdę widocznych tzn. nie zostały przysłonięte przez inne wieżowce. Przyjmujemy, że wieżowiec przysłania inny jeśli jest co najmniej takiej samej wysokości i znajduje się bliżej obserwatora. Pierwszy element określa wysokość najbliższego wieżowca.

Przykład

Kolejne budynki wzdłuż kierunku wzroku obserwatora to {2, 1, 3, 4, 1, 2, 3}. Oto graficzna ilustracja danych:

Ilustracja przykładu

Obserwator widzi jedynie trzy budynki chociaż jest ich siedem. Pierwszy budynek przysłania drugi, ale kolejne dwa są widoczne. Pozostałe zostały zasłonięte przez najwyższy wieżowiec. Rozpatrując podane zadanie z drugiej strony to będzie widać jedynie dwa budynki (3 i 4).

Implementacja

Pierwszy budynek jest zawsze widoczny, a każdy kolejny równej bądź mniejszej wysokości nie będzie widoczny. W przypadku napotkania wyższego wieżowca należy pamiętać o aktualizacji dotychczas maksymalnej wysokości, aby przysłaniał on kolejne budynki. Algorytm ma złożoność liniową O(n).

Oto przykładowa implementacja funkcji ileWiezowcow(), która dla przekazanej tablicy wysokości wieżowców zwraca ile z nich jest widoczna dla obserwatora.

1. def ileWiezowcow(lista):
2.   if (len(lista) == 0):
3.     return 0
4.   ile = 1
5.   max = lista[0]
6.   for el in lista:
7.     if (el > max):
8.       ile += 1
9.       max = el
10.   return ile

Na początku znajduje się wyróżniony przypadek, gdy lista jest pusta. Następnie zmienna ile przechowuję liczbę dotychczas widocznych wieżowców, a max - aktualnie najwyższy wieżowiec, który został napotkany.

Testowanie funkcji

W celu przetestowania funkcji można skorzystać z poniższego fragmentu kodu:

1. print("Podaj wysokości wieżowców:")
2. lista = [int(x) for x in input().split()]
3. wynik = ileWiezowcow(lista)
4. print("Widocznych budynków:", wynik)

• Kod źródłowy Implementacja