Mais alto que todos à direita
A missão
Problema
Uma fileira de prédios fica de frente para o mar, que está na ponta direita da fileira. Um prédio tem vista livre quando é estritamente mais alto que todos os prédios à sua direita. Dadas as alturas da esquerda para a direita, retorne as alturas dos prédios com vista livre, na mesma ordem, da esquerda para a direita.
Exemplos
Input: heights = [16, 17, 4, 3, 5, 2]
Output: [17, 5, 2]
Por quê: 17 e 5 superam tudo o que vem depois deles, e o último
prédio sempre tem vista
Input: heights = [5, 5, 3]
Output: [5, 3]
Por quê: o primeiro 5 é só tão alto quanto o segundo, não estritamente mais alto
Input: heights = []
Output: []
Por quê: edge case: uma fileira vazia não tem prédios para informar
Dicas
0 / 3
Comparar cada prédio com todos os que vêm depois dele compara muitos pares duas vezes. Que direção de percurso torna a pergunta fácil?
Percorrendo a partir da ponta direita, você só precisa lembrar um número sobre os prédios pelos quais já passou.
Varra do último índice até o primeiro, guardando a maior altura vista até agora. Um prédio é mantido quando é mais alto que esse máximo; atualize o máximo de qualquer forma e, no final, inverta as alturas mantidas.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(n)
Solução
A vista de um prédio depende só do prédio mais alto à sua direita, então varrer a partir da ponta direita com um máximo acumulado responde por cada prédio em um único passo. Um prédio estritamente acima do máximo acumulado é mantido, e o máximo passa a ser a altura dele. As alturas mantidas saem da direita para a esquerda, então uma única inversão restaura a ordem original. O tempo é O(n), e o espaço extra é O(1) fora a saída.
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([])) # -> []Travou na ideia, e não no código? O básico de arrays explica isso.