Más alto que todo lo que sigue
La misión
Problema
Una fila de edificios mira al mar, que está en el extremo derecho de la fila. Un edificio tiene vista despejada cuando es estrictamente más alto que todos los edificios a su derecha. Dadas las alturas de izquierda a derecha, devuelve las alturas de los edificios con vista despejada, en el mismo orden de izquierda a derecha.
Ejemplos
Input: heights = [16, 17, 4, 3, 5, 2]
Output: [17, 5, 2]
Por qué: 17 y 5 superan a todo lo que viene después, y el último
edificio siempre tiene vista
Input: heights = [5, 5, 3]
Output: [5, 3]
Por qué: el primer 5 solo es igual de alto que el segundo, no estrictamente más alto
Input: heights = []
Output: []
Por qué: caso límite: una fila vacía no tiene edificios que informar
Pistas
0 / 3
Comparar cada edificio con todo lo que viene después compara muchos pares dos veces. ¿Qué sentido de recorrido vuelve fácil la pregunta?
Si recorres desde el extremo derecho, solo necesitas recordar un número sobre los edificios que ya pasaste.
Recorre desde el último índice hasta el primero, llevando la altura máxima vista hasta ahora. Un edificio se conserva cuando es más alto que ese máximo; actualiza el máximo en cualquier caso e invierte las alturas conservadas al final.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(n)
Solución
La vista de un edificio depende solo del edificio más alto a su derecha, así que recorrer desde el extremo derecho con un máximo acumulado resuelve cada edificio en un solo paso. Un edificio estrictamente por encima del máximo acumulado se conserva, y el máximo sube hasta su altura. Las alturas conservadas salen de derecha a izquierda, así que una inversión restaura el orden original. El tiempo es O(n), y el espacio extra es O(1) sin contar la salida.
def clear_views(heights):
kept, tallest = [], float("-inf")
for i in range(len(heights) - 1, -1, -1): # right to left by index
if heights[i] > tallest:
kept.append(heights[i])
tallest = heights[i]
kept.reverse() # back to left-to-right order
return kept
print(clear_views([16, 17, 4, 3, 5, 2])) # -> [17, 5, 2]
print(clear_views([5, 5, 3])) # -> [5, 3]
print(clear_views([])) # -> []¿Lo que te frena es la idea y no el código? Fundamentos de arrays lo explica.