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. static int ileWiezowcow(int[] lista) {
2.   if (lista.Length == 0)
3.     return 0;
4.   int ile = 1;
5.   int max = lista[0];
6.   for (int i = 1; i < lista.Length; 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. static void Main(string[] args) {
2.   Console.WriteLine("Podaj wysokości wieżowców:");
3.   string[] dane = Console.ReadLine().Split(' ');
4.   int[] lista = new int[dane.Length];
5.   for (int i = 0; i < lista.Length; i++) {
6.     lista[i] = Convert.ToInt32(dane[i]);
7.   }
8.   int wynik = ileWiezowcow(lista);
9.   Console.WriteLine("Widocznych budynków {0}", wynik);
10.   Console.ReadKey();
11. }

• Kod źródłowy Implementacja