İçeriğe geç

İndirimden sonraki fiyatlar

Kolay#monotonic-stack#next-smaller~15 dk

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

Hedef zaman
O(n)
Hedef alan
O(n)

Kodda değil de fikirde mi takıldın? En büyük dikdörtgen bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case