İçeriğe geç

En ağır taşları parçala

Kolay#max-heap#simulation~20 dk

Görev tanımı

Problem

Bir taş yığını ağırlıklarıyla tarif ediliyor. Tekrar tekrar en ağır iki taşı al ve birbirine çarparak parçala: eşit taşlar birbirini tamamen yok eder, eşit olmayanlar ise farkı ağırlığında tek bir taş bırakır ve o da yığına geri döner. Kalan son taşın ağırlığını döndür; yığın boşalırsa 0 döndür.

Örnekler

Input:  stones = [2, 7, 4, 1, 8, 1]
Output: 1
Neden: 7 ile 8 1 bırakır, sonra 2 ile 4 2 bırakır, sonra 1 ile 2 1 bırakır, sonra 1 ile 1 yok olur
Input:  stones = [1, 1]
Output: 0
Neden: eşit iki taş birbirini yok eder, hiçbir şey kalmaz
Input:  stones = [3]
Output: 3
Neden: edge case: yalnız bir taşın çarpışacağı bir şey yok

İpuçları

0 / 3

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

Kodda değil de fikirde mi takıldın? Heap temelleri bunu anlatıyor.

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