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. int ileWiezowcow(vector<int> lista) {
2.   if (lista.size() == 0)
3.     return 0;
4.   int ile = 1;
5.   int max = lista[0];
6.   for (int i = 1; i < lista.size(); i++) {
7.     if (lista[i] > max) {
8.       ile++;
9.       max = lista[i];
10.     }
11.   }
12.   return ile;
13. }

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. int main () {
2.   int n, t;
3.   cout << "Ile elementow ma lista?\n n = ";
4.   cin >> n;
5.   vector<int> lista;
6.   for (int i = 0; i < n; i++) {
7.     cin >> t;
8.     lista.push_back(t);
9.   }
10.   int wynik = ileWiezowcow(lista);
11.   cout << "Widocznych bydunkow: " << wynik;
12.   system("pause");
13.   return 0;
14. }

• Kod źródłowy Implementacja