Sonrakilerin hepsinden uzun
Görev tanımı
Problem
Bir sıra bina, sıranın sağ ucundaki denize bakıyor. Bir bina, sağındaki her binadan daha uzunsa (aynı boy yetmez) açık bir manzaraya sahiptir. Soldan sağa yükseklikler verildiğinde, açık manzaralı binaların yüksekliklerini aynı soldan sağa sırayla döndür.
Örnekler
Input: heights = [16, 17, 4, 3, 5, 2]
Output: [17, 5, 2]
Neden: 17 ve 5 kendilerinden sonraki her şeyi geçer, son
bina da her zaman manzara görür
Input: heights = [5, 5, 3]
Output: [5, 3]
Neden: ilk 5 ikincisiyle yalnızca aynı boyda, daha uzun değil
Input: heights = []
Output: []
Neden: edge case: boş sırada raporlanacak bina yok
İpuçları
0 / 3
Her binayı kendisinden sonraki her şeyle karşılaştırmak birçok çifti iki kez karşılaştırır. Hangi ilerleme yönü soruyu kolaylaştırır?
Sağ uçtan dolaşırken, zaten geçtiğin binalara dair yalnız bir sayıyı hatırlaman gerekir.
Son indeksten ilkine doğru tara ve şimdiye kadar görülen en uzun yüksekliği tut. Bir bina o maksimumdan uzunsa tutulur; her iki durumda da maksimumu güncelle ve sonunda tutulan yükseklikleri ters çevir.
- Hedef zaman
- O(n)
- Hedef alan
- O(n)
Çözüm
Bir binanın manzarası yalnız sağındaki en uzun binaya bağlıdır; bu yüzden sağ uçtan kümülatif bir maksimumla taramak her binayı tek adımda cevaplar. Kümülatif maksimumu aşan bina tutulur ve maksimum ona yükseltilir. Tutulan yükseklikler sağdan sola çıktığı için tek bir ters çevirme orijinal sırayı geri getirir. Zaman O(n), çıktı dışında ek alan O(1).
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([])) # -> []Kodda değil de fikirde mi takıldın? Dizi temelleri bunu anlatıyor.