每日一题——LeetCode1046.最后一块石头的重量

方法一 暴力排序

保证数组从小到大排序，所以最后两个就是最大的石头，每次取最后两个元素进行比较，一样重就直接下一次循环，不一样重就把两个石头重量差push进数组，把数组再次排序

循序嵌套sort排序时间复杂度较高，只是本题测试数据量小才能通过

var lastStoneWeight = function(stones) {
    stones.sort((a,b)=>a-b)
    while(stones.length>1){
       var s1= stones.pop(),
       s2= stones.pop()
       if(s1>s2){
           stones.push(s1-s2)
           stones.sort((a,b)=>a-b)
           console.log(stones)
       }
    }
     if(stones.length===1) return stones[0]
     else return 0
};

?消耗时间和内存情况：

方法二 官方解法（力扣官方题解）

????????将所有石头的重量放入最大堆中。每次依次从队列中取出最重的两块石头 a 和 b，必有 a≥b。如果 a>b，则将新石头 a?b放回到最大堆中；如果 a=b，两块石头完全被粉碎，因此不会产生新的石头。重复上述操作，直到剩下的石头少于 2?块。

????????最终可能剩下 1?块石头，该石头的重量即为最大堆中剩下的元素，返回该元素；也可能没有石头剩下，此时最大堆为空，返回 0。

Leetcode内置了?@datastructures-js/priority-queue?库。

我们可以使用以下代码新建一个最大优先队列。

let queue = new MaxPriorityQueue()

插入数据和得到最大值，我们分别用enqueue和dequeue方法即可

queue.enqueue(1)

queue.enqueue(1)

let max = queue.dequeue()

PriorityQueue基于堆，可以实现我们一往里加数，它内部就会自动排序

var lastStoneWeight = function(stones) {
    const pq = new MaxPriorityQueue();
    for (const stone of stones) {
        pq.enqueue('x', stone);
    }
    
    while (pq.size() > 1) {
        const a = pq.dequeue()['priority'];
        const b = pq.dequeue()['priority'];
        if (a > b) {
            pq.enqueue('x', a - b);
        }
    }
    return pq.isEmpty() ? 0 : pq.dequeue()['priority'];
};

消耗时间和内存情况：

?