you are given an array of integers stones where stones[i] is the weight of the ith stone.
We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:
If x == y, both stones are destroyed, and
If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.
At the end of the game, there is at most one stone left.
Return the weight of the last remaining stone. If there are no stones left, return 0.
Example 1:
Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation:
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.
var lastStoneWeight = function (stones) {
const stonesQueue = new MaxPriorityQueue();
for (let i = 0; i < stones.length; i++) {
stonesQueue.enqueue(stones[i]);
}
while (stonesQueue.size() > 1) {
let y = stonesQueue.dequeue().element;
let x = stonesQueue.dequeue().element;
y = y - x;
stonesQueue.enqueue(y);
}
return stonesQueue.dequeue().element;
};
// time: O(nlogn)
// space: O(n)
// Solution 2
/**
* @param {number[]} stones
* @return {number}
*/
class MaxHeap {
constructor(values) {
this.values = [null, ...values];
this.heapify();
}
heapify() {
for (let i = Math.floor(this.values.length / 2); i > 0; i--) {
this.heapifyDown(i);
}
}
addToHeap(val) {
this.values.push(val);
this.heapifyUp(this.values.length - 1);
}
heapifyUp(index) {
let parentIndex = Math.floor(index / 2);
while (this.values[parentIndex] !== null) {
if (this.values[index] > this.values[parentIndex]) {
let temp = this.values[index];
this.values[index] = this.values[parentIndex];
this.values[parentIndex] = temp;
}
index = parentIndex;
parentIndex = Math.floor(index / 2);
}
}
heapifyDown(index) {
let leftChildIndex = 2 * index;
let rightChildIndex = 2 * index + 1;
let largerIndex;
while (
leftChildIndex < this.values.length ||
rightChildIndex < this.values.length
) {
if (leftChildIndex >= this.values.length) {
largerIndex = rightChildIndex;
} else if (rightChildIndex >= this.values.length) {
largerIndex = leftChildIndex;
} else {
if (this.values[leftChildIndex] >= this.values[rightChildIndex]) {
largerIndex = leftChildIndex;
} else {
largerIndex = rightChildIndex;
}
}
if (this.values[index] < this.values[largerIndex]) {
let temp = this.values[index];
this.values[index] = this.values[largerIndex];
this.values[largerIndex] = temp;
index = largerIndex;
leftChildIndex = 2 * index;
rightChildIndex = 2 * index + 1;
} else {
break;
}
}
}
extractMaxValue() {
let tempValue = this.values[1];
this.values[1] = this.values[this.values.length - 1];
this.values[this.values.length - 1] = tempValue;
let maxValue = this.values.pop();
this.heapifyDown(1);
return maxValue;
}
}
var lastStoneWeight = function (stones) {
let maxHeap = new MaxHeap(stones);
while (maxHeap.values.length > 2) {
let max1 = maxHeap.extractMaxValue();
let max2 = maxHeap.extractMaxValue();
let absoluteDiff = Math.abs(max1 - max2);
if (absoluteDiff) {
maxHeap.addToHeap(absoluteDiff);
}
}
if (maxHeap.values.length === 1) {
return 0;
}
return maxHeap.values[1];
};
Oldest comments (0)