Sponsored
Sponsored
This approach uses a max-heap (priority queue) to efficiently track and retrieve the two heaviest stones. By inserting stones with negative values, we use a min-heap implementation in certain languages to simulate max-heap behavior.
Time Complexity: O(n log n), where n is the number of stones. This accounts for the heap operations.
Space Complexity: O(n), to maintain the heap of stones.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int LastStoneWeight(int[] stones) {
6 PriorityQueue<int, int> maxHeap = new();
7 foreach (int stone in stones) {
8 maxHeap.Enqueue(stone, -stone);
9 }
10 while (maxHeap.Count > 1) {
11 int first = maxHeap.Dequeue();
12 int second = maxHeap.Dequeue();
13 if (first != second) {
14 maxHeap.Enqueue(first - second, -(first - second));
15 }
16 }
17 return maxHeap.Count == 0 ? 0 : maxHeap.Dequeue();
18 }
19}The C# solution makes use of PriorityQueue to maintain stone weights for easy comparison and prioritization, ensuring efficient retrieval and update of stone weights until one or none are left.
This approach uses a multiset or bag (analogous to balanced trees or sorted lists in some languages) to manage dynamically sorted stone weights. This allows for direct access to largest elements and supports efficient inserts/removals without full re-sorting.
Time Complexity: O(n^2), due to insert and remove operations in SortedList being O(log n).
Space Complexity: O(n), for storage within the SortedList.
1#include <vector>
class Solution {
public:
int lastStoneWeight(std::vector<int>& stones) {
std::multiset<int> sortedStones(stones.begin(), stones.end());
while (sortedStones.size() > 1) {
auto it1 = std::prev(sortedStones.end());
int first = *it1; sortedStones.erase(it1);
auto it2 = std::prev(sortedStones.end());
int second = *it2; sortedStones.erase(it2);
if (first != second) {
sortedStones.insert(first - second);
}
}
return sortedStones.empty() ? 0 : *sortedStones.begin();
}
};Using std::multiset in C++, sorted access is granted with prev functions utilized for efficient retrieval and organization addressing of the stones as differences arise.