İndirimden sonraki fiyatlar
Görev tanımı
Problem
Bir mağaza ürün fiyatlarını raf sırasıyla listeliyor. i ürününü almak, sağındaki fiyatı prices[i]'den küçük ya da ona eşit olan ilk ürünün fiyatı kadar indirim kazandırıyor. Böyle bir ürün yoksa indirim yok. Her ürün için gerçekte ödenen fiyatı döndür.
Örnekler
Input: prices = [8, 4, 6, 2, 3]
Output: [4, 2, 4, 2, 3]
Neden: 8'e 4, 4'e ve 6'ya 2'şer indirim uygulanıyor; 2 ve 3'ten sonra daha ucuz ürün yok
Input: prices = [10, 1, 1, 6]
Output: [9, 0, 1, 6]
Neden: eşit bir fiyat sayılır, bu yüzden ilk 1'e ikinci 1 kadar indirim uygulanır
Input: prices = [1, 2, 3, 4, 5]
Output: [1, 2, 3, 4, 5]
Neden: edge case: artan fiyatlar sağda hiç daha ucuz bir ürünle karşılaşmaz
İpuçları
0 / 3
Her ürün için sağındaki büyük olmayan ilk fiyata ihtiyacın var. Her ürünü kendisinden sonraki her şeyle kontrol etmek karesel. Herhangi bir anda hangi ürünler hâlâ indirimini bekliyor?
Bir ürün kendi fiyatı ya da altında bir fiyat göründüğü anda beklemeyi bırakır. Hâlâ bekleyen ürünlerin fiyatları alttan üste her zaman artar, bu yüzden yeni bir fiyat onları yukarıdan aşağı çözer.
İndekslerden oluşan bir stack tut. Her yeni fiyat için fiyatı ondan büyük ya da ona eşit olan her indeksi pop et ve yeni fiyatı o üründen çıkar. Sonra yeni indeksi push et. Stack'te kalan ürünler tam fiyatlarını korur.
- Hedef zaman
- O(n)
- Hedef alan
- O(n)
Çözüm
Bu, Largest Rectangle'ın her çubuğun nerede durduğunu bulmak için çalıştırdığı sonraki küçük eleman taramasının aynısı. İndeksler artan fiyatlarla bir stack'te bekler ve bir ürünün kendi fiyatında ya da altındaki ilk fiyat onu pop edip indirimini sabitler. Hiç pop edilmeyen bir ürünün sağında daha ucuz bir ürün yoktur, bu yüzden fiyatını korur; sonucun girdinin bir kopyası olarak başlamasının sebebi bu. Her indeks en fazla bir kez push ve pop edilir; zaman O(n), alan O(n).
def final_prices(prices):
paid = prices[:] # no discount unless one is found
stack = [] # waiting indices, prices rising upward
for i, p in enumerate(prices):
while stack and prices[stack[-1]] >= p: # p is the first price at or below theirs
j = stack.pop()
paid[j] = prices[j] - p
stack.append(i)
return paid
print(final_prices([8, 4, 6, 2, 3])) # -> [4, 2, 4, 2, 3]
print(final_prices([10, 1, 1, 6])) # -> [9, 0, 1, 6]
print(final_prices([1, 2, 3, 4, 5])) # -> [1, 2, 3, 4, 5]Kodda değil de fikirde mi takıldın? En büyük dikdörtgen bunu anlatıyor.