Número de edificios que dan al sol

Dada una array que representa las alturas de los edificios. La array tiene edificios de izquierda a derecha como se muestra en el siguiente diagrama, cuente el número de edificios que miran hacia la puesta del sol. Se supone que las alturas de todos los edificios son distintas.

Ejemplos: 

Input : arr[] = {7, 4, 8, 2, 9}
Output: 3
Explanation: As 7 is the first element, it can 
see the sunset.
4 can't see the sunset as 7 is hiding it. 
8 can see.
2 can't see the sunset.
9 also can see the sunset.

Input : arr[] = {2, 3, 4, 5}
Output : 4

Preguntado en: Amazon Entrevista

Se puede observar fácilmente que solo el elemento máximo encontrado hasta ahora verá la luz del sol 
, es decir, curr_max verá la luz del sol y luego solo el elemento mayor que curr_max verá la luz del sol. Atravesamos la array dada de izquierda a derecha. Realizamos un seguimiento del elemento máximo visto hasta ahora. Siempre que un elemento supere el máximo actual, aumente el resultado y actualice el máximo actual.

Implementación:

// C++ program to count buildings that can
// see sunlight.
#include <iostream>
using namespace std;
 
// Returns count buildings
// that can see sunlight
int countBuildings(int arr[], int n)
{
    // Initialize result (Note that first building
    // always sees sunlight)
    int count = 1;
 
    // Start traversing element
    int curr_max = arr[0];
    for (int i = 1; i < n; i++) {
       
        // If curr_element is maximum
        // or current element is
        // equal, update maximum and increment count
        if (arr[i] > curr_max || arr[i] == curr_max) {
            count++;
            curr_max = arr[i];
        }
    }
 
    return count;
}
 
// Driver code
int main()
{
    int arr[] = { 7, 4, 8, 2, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << countBuildings(arr, n);
    return 0;
}

// Java program to count buildings that can
// see sunlight.
 
class Test {
    // Returns count buildings that can see sunlight
    static int countBuildings(int arr[], int n)
    {
        // Initialize result  (Note that first building
        // always sees sunlight)
        int count = 1;
 
        // Start traversing element
        int curr_max = arr[0];
        for (int i = 1; i < n; i++) {
           
            // If curr_element is maximum
            // or current element
            // is equal, update maximum and increment count
            if (arr[i] > curr_max || arr[i] == curr_max) {
                count++;
                curr_max = arr[i];
            }
        }
 
        return count;
    }
 
    // Driver method
    public static void main(String[] args)
    {
        int arr[] = { 7, 4, 8, 2, 9 };
 
        System.out.println(countBuildings(arr, arr.length));
    }
}

# Python3 program to count buildings
# that can see sunlight.
 
# Returns count buildings that
# can see sunlight
 
 
def countBuildings(arr, n):
 
    # Initialize result (Note that first
    # building always sees sunlight)
    count = 1
 
    # Start traversing element
    curr_max = arr[0]
    for i in range(1, n):
 
        # If curr_element is maximum or
        # current element is equal,
        # update maximum and increment count
        if (arr[i] > curr_max or arr[i] == curr_max):
 
            count += 1
            curr_max = arr[i]
 
    return count
 
 
# Driver code
arr = [7, 4, 8, 2, 9]
n = len(arr)
print(countBuildings(arr, n))
 
# This code is contributed by Rohit.

// C# program to count buildings that can
// see sunlight.
using System;
 
class GFG {
   
    // Returns count buildings
    // that can see sunlight
    static int countBuildings(int[] arr, int n)
    {
         
        // Initialize result (Note that first building
        // always sees sunlight)
        int count = 1;
 
        // Start traversing element
        int curr_max = arr[0];
        for (int i = 1; i < n; i++) {
           
            // If curr_element is maximum
            // or current element
            // is equal, update maximum
            // and increment count
            if (arr[i] > curr_max || arr[i] == curr_max) {
                count++;
                curr_max = arr[i];
            }
        }
 
        return count;
    }
 
    // Driver method
    public static void Main()
    {
        int[] arr = { 7, 4, 8, 2, 9 };
 
        Console.Write(countBuildings(arr, arr.Length));
    }
}
 
// This code is contributed by Rohit.

<?php
// php program to count buildings
// that can see sunlight.
 
// Returns count buildings that
// can see sunlight
function countBuildings($arr, $n)
{
    // Initialize result (Note that
    // first building always sees
    // sunlight)
    $count = 1;
 
    // Start traversing element
    $curr_max = $arr[0];
    for ( $i = 1; $i < $n; $i++)
    {
         
        // If curr_element is maximum or
        // current element is equal,
        // update maximum and
        // increment count
        if ($arr[$i] > $curr_max || $arr[$i] == $curr_max)
        {
            $count++;
            $curr_max=$arr[$i];
        }
    }
 
    return $count;
}
 
// Driver code
$arr = array(7, 4, 8, 2, 9);
$n = sizeof($arr) / sizeof($arr[0]);
echo countBuildings($arr, $n);
 
// This code is contributed by
// Rohit
?>

<script>
 
// Javascript program to count buildings that can
// see sunlight.
 
// Returns count buildings
// that can see sunlight
function countBuildings( arr, n)
{
    // Initialize result (Note that first building
    // always sees sunlight)
    let count = 1;
 
    // Start traversing element
    let curr_max = arr[0];
    for (let i = 1; i < n; i++) {
       
        // If curr_element is maximum
        // or current element is
        // equal, update maximum and increment count
        if (arr[i] > curr_max || arr[i] == curr_max) {
            count++;
            curr_max = arr[i];
        }
    }
 
    return count;
}
 
     
    // Driver program
     
    let arr = [ 7, 4, 8, 2, 9 ];
    let n = arr.length;
    document.write(countBuildings(arr, n));
        
</script>

3

Complejidad temporal: O(n) 
Espacio auxiliar: O(1)

Este artículo es una contribución de Sahil Chhabra . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.