1046-Last-Stone-Weight.cs

publicclassSolution
{
privatePriorityQueue<int,int>pq;

// T: O(NLogN)
publicintLastStoneWeight(int[]stones)
{
pq=newPriorityQueue<int,int>(newMaxHeapComparer());

AddStones(stones);
ComputeLastStoneWeight();

returnpq.Count==0?0:pq.Dequeue();
}


privatevoidAddStones(int[]stones)
{
foreach(varstoneinstones)
{
// T: Heapify is O(N) for every enqueued item
pq.Enqueue(stone,stone);
}
}

// T: O(NLogN), to get max value its O(LogN) and we perform this for N items => O(NLogN)
privatevoidComputeLastStoneWeight()
{
while(pq.Count>1)
{
vary=pq.Dequeue();
varx=pq.Dequeue();

if(x!=y)
{
vardiff=y-x;
pq.Enqueue(diff,diff);
}
}
}

publicclassMaxHeapComparer:IComparer<int>
{
publicintCompare(intx,inty)
{
returny-x;
}
}
}