【Day 86 】2022-03-07 - 1046.最后一块石头的重量

[azl397985856]

1046.最后一块石头的重量

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/last-stone-weight/

前置知识

• 堆

  题目描述

  
  有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎； 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

 

示例：

输入：[2,7,4,1,8,1] 输出：1 解释： 先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]， 再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]， 接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]， 最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。  

提示：

1 <= stones.length <= 30 1 <= stones[i] <= 1000

[mannnn6]

class Solution {
    public int lastStoneWeight(int[] stones) {
            Queue<Integer> maxPq = new PriorityQueue<>(stones.length, Comparator.reverseOrder());
            for (int stone : stones) {
                maxPq.add(stone);
            }
            while (maxPq.size() >= 2) {
                int y = maxPq.poll();
                int x = maxPq.poll();
                if (y > x) {
                    maxPq.add(y - x);
                }
            }
            return maxPq.isEmpty() ? 0 : maxPq.peek();
        }
}

[zwx0641]

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> q;
        for (auto& s : stones) {
            q.push(s);
        }

        while (q.size() > 1) {
            int x = q.top();
            q.pop();
            int y = q.top();
            q.pop();
            if (x > y)
                q.push(x - y);
        }
        return q.empty() ? 0 : q.top();
    }
};

[cszys888]

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        stones = [-x for x in stones]
        heapq.heapify(stones)
        while len(stones) >= 2:
            heavy = heapq.heappop(stones)
            light = heapq.heappop(stones)
            if heavy == light:
                continue
            else:
                heapq.heappush(stones, heavy - light)
        return -stones[0] if stones else 0

time complexity: O(n*logn) space complexity: O(logn)

[ZhangNN2018]

class Solution(object):
    def lastStoneWeight(self, stones):
        """
        :type stones: List[int]
        :rtype: int
        """
        while len(stones) > 1:
            stones.sort()
            if stones[-1] == stones[-2]:
                stones.pop(-1)
                stones.pop(-1)
            else:
                stones[-2] = abs(stones[-1] - stones[-2])
                stones.pop(-1)
        if len(stones) == 0:
            return 0
        else:
            return stones[0]

[falconruo]

思路:

大顶堆

复杂度分析:

• 时间复杂度: O(N * logN)，N为数组stones的长度
• 空间复杂度: O(N)

代码(C++):

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq;

        for (int i = 0; i < stones.size(); ++i) {
            pq.push(stones[i]);
        }

        while (!pq.empty()) {
            int w1 = pq.top(); pq.pop();
            if (pq.empty()) return w1;
            int w2 = pq.top(); pq.pop();

            if (w1 != w2) {
                pq.push(abs(w1 - w2));
            }
        }

        return 0;
    }
};

[Tesla-1i]

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        stones = [-x for x in stones]
        heapq.heapify(stones)
        while len(stones) >= 2:
            heavy = heapq.heappop(stones)
            light = heapq.heappop(stones)
            if heavy == light:
                continue
            else:
                heapq.heappush(stones, heavy - light)
        return -stones[0] if stones else 0

[yan0327]

type hp []int
func (h hp) Len() int {return len(h)}
func (h hp) Less(i,j int) bool {return h[i] > h[j]}
func (h hp) Swap(i,j int) {h[i],h[j] = h[j],h[i]}
func (h *hp) Push(x interface{}){*h = append(*h,x.(int))}
func (h *hp) Pop() interface{}{
    x := *h
    out := x[len(x)-1]
    *h = x[:len(x)-1]
    return out
}
func lastStoneWeight(stones []int) int {
    h := &hp{}
    heap.Init(h)
    for _,x := range stones{
        heap.Push(h,x)
    }
    for h.Len() >= 2{
        node1 := heap.Pop(h).(int)
        node2 := heap.Pop(h).(int)
        if node1-node2>0{
            heap.Push(h, node1-node2)
        }
    }
    if h.Len() == 1{
        return heap.Pop(h).(int)
    }
    return 0
}

[1149004121]

1046. 最后一块石头的重量

思路

最大堆。

代码

var lastStoneWeight = function(stones) {
    let heap = new MaxPriorityQueue();
    for(const stone of stones){
        heap.enqueue("x", stone);
    }
    while(heap.size() >= 2){
        let y = heap.dequeue()["priority"];
        let x = heap.dequeue()["priority"];
        if(x !== y) heap.enqueue("x", y - x);
    };
    return heap.size() === 1 ? heap.dequeue()["priority"]: 0;
};

复杂度分析

• 时间复杂度：O( N*logN ) 。
• 空间复杂度：O(N) 。

[xuhzyy]

class Solution(object):
    def lastStoneWeight(self, stones):
        """
        :type stones: List[int]
        :rtype: int
        """
        h = []
        for stone in stones:
            heapq.heappush(h, -stone)

        while(len(h) > 1):
            x, y = -heapq.heappop(h), -heapq.heappop(h)
            if x != y:
                heapq.heappush(h, -abs(x-y))
        return -h[0] if len(h) else 0

[Alexno1no2]

# python中有heapq能创建小顶堆，把数据取反变成负数间接实现大顶堆

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        for i in range(len(stones)):
            stones[i] = -stones[i];
        heapify(stones)
        while len(stones) > 0:
            y = -heappop(stones)
            if len(stones) == 0:
                return y
            x = -heappop(stones)
            if x != y:
                heappush(stones, x - y)
        return 0

[ZJP1483469269]

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        p = []
        n = len(stones)
        for s in stones:
            heappush(p , -s)
        while len(p) > 1:
            a , b = heappop(p) , heappop(p)
            heappush(p  , a - b)

        return -p[0]

[wdwxw]

class Solution { public int lastStoneWeight(int[] stones) { PriorityQueue pq = new PriorityQueue((a, b) -> b - a); for (int stone : stones) { pq.offer(stone); }

    while (pq.size() > 1) {
        int a = pq.poll();
        int b = pq.poll();
        if (a > b) {
            pq.offer(a - b);
        }
    }
    return pq.isEmpty() ? 0 : pq.poll();
}

}

[ZacheryCao]

Idea

heap

Code

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        heap = [-i for i in stones]
        heapq.heapify(heap)
        while len(heap)>1:
            heapq.heappush(heap, -abs(heapq.heappop(heap)-heapq.heappop(heap)))
        return -heap[0]

Complexity:

Time: O(n logn) Space: O(n)

[rzhao010]

class Solution {
    public int lastStoneWeight(int[] stones) {
        // using maxHeap to store all the stones, each time pick up two and process
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        for (int n: stones) {
            maxHeap.add(n);
        }
        while(maxHeap.size() > 1) {
            int y = maxHeap.poll();
            int x = maxHeap.poll();
            if (x < y) {
                y = y - x;
                maxHeap.add(y);
            }
        }
        return maxHeap.isEmpty() ? 0: maxHeap.peek();
    }
}

Complexity Time: O(nlogn), we picked up n - 1 stones from list, and operation for heap is logn Space: O(n)

[charlestang]

思路

最大堆，模拟。

用一个最大堆，模拟每轮碎石过程。

时间复杂度 O(n logn)

空间复杂度 O(n)

代码

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        q = []

        for stone in stones:
            heapq.heappush(q, -stone)

        while len(q) > 1:
            x = -heapq.heappop(q)
            y = -heapq.heappop(q)
            if x != y:
                heapq.heappush(q, -abs(x - y))

        return -q[0] if q else 0

[KennethAlgol]

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
        for (int stone : stones) {
            pq.offer(stone);
        }

        while (pq.size() > 1) {
            int a = pq.poll();
            int b = pq.poll();
            if (a > b) {
                pq.offer(a - b);
            }
        }
        return pq.isEmpty() ? 0 : pq.poll();
    }
}

[xinhaoyi]

class Solution { public int lastStoneWeight(int[] stones) { / 使用优先对列保证每次能拿到最大的数 / Queue queue = new PriorityQueue<>(new Comparator() { @Override public int compare(Integer o1, Integer o2) { return (o2 - o1); } }); for (int i = 0; i < stones.length; i++) { queue.offer(stones[i]); } while(queue.size() > 1) { int x = queue.poll(); int y = queue.poll(); int diff = Math.abs(x - y); if (diff != 0) { queue.offer(diff); } } if (queue.isEmpty()) return 0; return queue.peek(); } }

[zjsuper]

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # max heap
        stones = [-i for i in stones]
        heapq.heapify(stones)   
        while len(stones) > 1:
            a,b = heapq.heappop(stones),heapq.heappop(stones)
            if a == b:
                pass
            else:
                temp = a-b
                heapq.heappush(stones,temp)
        if not stones:
            return 0
        else:
            return -stones[0]

[ACcentuaLtor]

class Solution: def lastStoneWeight(self, stones: List[int]) -> int:

初始化

    heap = [-stone for stone in stones]
    heapq.heapify(heap)

    # 模拟
    while len(heap) > 1:
        x,y = heapq.heappop(heap),heapq.heappop(heap)
        if x != y:
            heapq.heappush(heap,x-y)

    if heap: return -heap[0]
    return 0

[LannyX]

思路

PQ

代码

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
        for(int s : stones){
            pq.offer(s);
        }
        while(pq.size() > 1){
            int a = pq.poll();
            int b = pq.poll();
            if(a > b){
                pq.offer(a - b);
            }
        }
        return pq.isEmpty() ? 0 : pq.poll();
    }
}

复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

[alongchong]

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
        for (int stone : stones) {
            pq.offer(stone);
        }

        while (pq.size() > 1) {
            int a = pq.poll();
            int b = pq.poll();
            if (a > b) {
                pq.offer(a - b);
            }
        }
        return pq.isEmpty() ? 0 : pq.poll();
    }
}

[JudyZhou95]

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        neg_stones = [-x for x in stones]
        heapq.heapify(neg_stones)

        while len(neg_stones) >= 2:
            x = -heapq.heappop(neg_stones)
            y = -heapq.heappop(neg_stones)

            if x == y:
                continue
            else:
                diff = abs(x - y)

            heapq.heappush(neg_stones, -diff)

        if neg_stones:
            return -neg_stones[0]
        else:
            return 0

[QinhaoChang]

class Solution: def lastStoneWeight(self, stones: List[int]) -> int: import heapq

    maxheap = []

    for i in range(len(stones)):
        heapq.heappush(maxheap, -stones[i])

    while len(maxheap) > 1:
        a = -heapq.heappop(maxheap)
        b = -heapq.heappop(maxheap)

        if a != b:
            heapq.heappush(maxheap, -(a - b))

    return -maxheap[-1] if maxheap else 0

[xjhcassy]

class Solution {

    public int lastStoneWeight(int[] stones) {

        PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);

        for (int i : stones)
            pq.offer(i);

        while (pq.size() >= 2) {

            int x = pq.poll();
            int y = pq.poll();

            if (x > y)
                pq.offer(x - y);
        }

        return pq.size() == 1 ? pq.peek() : 0;
    }
}

[last-Battle]

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> q;
        for (int s: stones) {
            q.push(s);
        }

        while (q.size() > 1) {
            int a = q.top();
            q.pop();
            int b = q.top();
            q.pop();
            if (a > b) {
                q.push(a - b);
            }
        }
        return q.empty() ? 0 : q.top();
    }
};

[GaoMinghao]

思路

堆

代码

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        for(int stone: stones)
            heap.add(stone);
        while(heap.size()>=2) {
            int s1 = heap.poll();
            int s2 = heap.poll();
            if(s1 != s2) {
                heap.add(s1-s2);
            }
        }
        if(heap.isEmpty())
            return 0;
        else
            return heap.poll();
    }
}

[shamworld]

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"];
};

[guangsizhongbin]

func lastStoneWeight(stones []int) int { var l int l = len(stones) if l == 0 { return 0 }

for ; l > 1; l = len(stones) {
    sort.Ints(stones)

    x := stones[l-2]
    y := stones[l-1]
    if x == y {
        stones = stones[0:l-2]
    } else {
        stones = append(stones[0:l-2], y-x)
    }

}

result := 0
if len(stones) > 0 {
    result = stones[0]
}
return result

}

[zzzpppy]

public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        for (int stone : stones)
            pq.offer(stone);
        int distant = 0;
        while (pq.size() > 1)
            if ((distant = pq.poll() - pq.poll()) > 0)
                pq.offer(distant);
        return pq.isEmpty() ? 0 : pq.poll();
    }

[callmeerika]

思路

大根堆

代码

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'];
};

复杂度

时间复杂度：O(nlogn)
空间复杂度：O(n)

[Riuusee]

思路

堆

代码

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
        for (int stone : stones) {
            pq.offer(stone);
        }

        while (pq.size() > 1) {
            int a = pq.poll();
            int b = pq.poll();
            if (a > b) {
                pq.offer(a - b);
            }
        }
        return pq.isEmpty() ? 0 : pq.poll();
    }
}

复杂度分析

• 时间复杂度: O(nlogn)
• 空间复杂度: O(n)

[hdyhdy]

func lastStoneWeight(stones []int) int {
    if len(stones) == 1 {
        return stones[0]
    }
    h := &hp{}
    heap.Init(h)

    for _,k := range stones{
        heap.Push(h,k)
    }

    for h.Len() > 1 {
        tem1 :=heap.Pop(h).(int)
        tem2 :=heap.Pop(h).(int)
        tem := tem1 - tem2
        if tem != 0 {
            heap.Push(h,tem)
        }
    }
    if h.Len() == 1{
        return heap.Pop(h).(int)
    }
    return 0
}

type hp []int 

func (h hp)Len() int{
    lenh := len(h)
    return lenh
}

func (h hp)Less(i,j int)bool{
    return h[i] > h[j]
}

func (h hp)Swap(i,j int) {
    h[i],h[j] = h[j],h[i]
}

func(h *hp)Push (i interface{}) {
    *h = append(*h,i.(int))
}

func (h *hp)Pop() interface{}{
    x := *h
    ans := x[len(x) - 1]
    *h = x[:len(x) - 1]
    return ans 
}

[AIBotao]

class Solution: def lastStoneWeight(self, stones: List[int]) -> int: stones = [-x for x in stones] heapq.heapify(stones) while len(stones) >= 2: heavy = heapq.heappop(stones) light = heapq.heappop(stones) if heavy == light: continue else: heapq.heappush(stones, heavy - light) return -stones[0] if stones else 0

[googidaddy]

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'];

};

[yetfan]

思路

堆排序

1. 多余1个，每次取两个最大的，比较大小（相同则重新开始1，否则求差值，重新加入堆）
2. 剩一个，返回其值
3. 不剩了，返回0

代码

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        q = [-i for i in stones]
        heapq.heapify(q)
        while len(q) > 1:
            s1 = heapq.heappop(q)
            s2 = heapq.heappop(q)
            if s1 == s2:
                continue
            else:
                heapq.heappush(q, -abs(s1-s2))
        if len(q) == 1:
            return -heapq.heappop(q)
        return 0

复杂度 时间 O(nlogn) 空间 O(n)

[fornobugworld]

class Solution:
    import heapq
    def lastStoneWeight(self, stones: List[int]) -> int:
        hp = []
        for i in stones:
            heappush(hp,-i)
        for i in range(len(stones)-1):
            y = -heappop(hp)
            x = -heappop(hp)
            heappush(hp,x-y)
        return -heappop(hp)

[Jay214]

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeight = function (stones) {
    let maxHeap = new MaxHeap();
    for (let i = 0; i < stones.length; i++) {
        maxHeap.buildHeap(stones[i])
    }
    while (true) {
        if (maxHeap.heapEmpty()) {
            return 0;
        }
        if (maxHeap.onlyOne()) {
            return maxHeap.getTop();
        }
        let y = maxHeap.popTop();
        let x = maxHeap.popTop();
        if (x !== y) {
            maxHeap.buildHeap(y - x)
        }
    }
};

class MaxHeap {
    constructor() {
        this.data = [0];
        this.count = 0;
    }

    buildHeap(stone) {
        this.count++;
        this.data[this.count] = stone;
        let i = this.count;
        while (parseInt(i / 2) > 0 && this.data[i] > this.data[parseInt(i / 2)]) {
            this.swap(i, parseInt(i / 2));
            i = parseInt(i / 2);
        }
    }

    swap(i, j) {
        let temp = this.data[i];
        this.data[i] = this.data[j];
        this.data[j] = temp;
    }

    popTop() {
        let top = this.data[1];
        this.data[1] = this.data[this.count];
        this.data.splice(this.count, 1)
        this.count--;
        let i = 1;
        while (true) {
            let maxPos = i;
            if (i * 2 <= this.count && this.data[i] < this.data[i * 2]) {
                maxPos = i * 2;
            }
            if (i * 2 + 1 <= this.count && this.data[maxPos] < this.data[i * 2 + 1]) {
                maxPos = i * 2 + 1;
            }
            if (i === maxPos) {
                break;
            }
            this.swap(i, maxPos);
            i = maxPos;
        }
        return top;
    }

    heapEmpty() {
        return this.count === 0;
    }

    onlyOne() {
        return this.count === 1;
    }

    getTop() {
        return this.data[1];
    }
}

[taojin1992]

// time: O(nlogn), n = stones.length
// space: O(n)

class Solution {
    public int lastStoneWeight(int[] stones) {
        if (stones.length == 1) return stones[0];
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> (b - a));
        for (int stone : stones) {
            maxHeap.offer(stone);
        }
        while (maxHeap.size() > 1) {
            int max = maxHeap.poll();
            int submax = maxHeap.poll();
            if (max != submax) {
                maxHeap.offer(max - submax);
            }
        }
        return maxHeap.size() == 0 ? 0 : maxHeap.poll();
    }
}

[machuangmr]

代码

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
        for (int stone : stones) {
            pq.offer(stone);
        }

        while (pq.size() > 1) {
            int a = pq.poll();
            int b = pq.poll();
            if (a > b) {
                pq.offer(a - b);
            }
        }
        return pq.isEmpty() ? 0 : pq.poll();
    }
}

[for123s]

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> q;
        for(int i=0;i<stones.size();++i)
            q.push(stones[i]);
        int a, b;
        while(q.size()>1)
        {
            a = q.top();
            q.pop();
            b = q.top();
            q.pop();
            q.push(a-b);
        }
        return q.top();
    }
};

[Richard-LYF]

class Solution: def lastStoneWeight(self, stones: List[int]) -> int: h = [-stone for stone in stones] heapq.heapify(h)

    while len(h) > 1:
        a, b = heapq.heappop(h), heapq.heappop(h)
        if a != b:
            heapq.heappush(h, a - b)

    return -h[0] if h else 0

[dahaiyidi]

Problem

[1046. 最后一块石头的重量](https://leetcode-cn.com/problems/last-stone-weight/)

++

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

示例：

输入：[2,7,4,1,8,1]
输出：1
解释：
先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。

---

Note

• 最大堆

---

Complexity

• 时间O：nlogn
• 空间O：n

---

Python

C++

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> q;
        for(auto i: stones){
            q.push(i);
        }

        while(q.size() >= 2){
            int p1 = q.top();
            q.pop();
            int p2 = q.top();
            q.pop();
            int temp = abs(p1 - p2);
            if(temp != 0){
                q.push(temp);
            }
        }
        return q.empty()? 0: q.top();
    }
};

From : https://github.com/dahaiyidi/awsome-leetcode

[tian-pengfei]

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {

        priority_queue<int,vector<int>,less<int>> q;
        q.emplace();
        for(auto const a: stones ){
            q.push(a);
        }
        while(q.size()>1){

            int a = q.top();
           q.pop();

           int b = q.top();
           q.pop();

           int c = abs(a-b);
            q.push(c);

        }
        return q.top();
    }
};

[declan92]

思路

1. 将数组元素添加进大堆顶;
2. 堆size>1时,pop取出两个元素,按照题目要求模拟,如果x!=y,将y-x offer进入堆;

java

class Solution {
    public int lastStoneWeight(int[] stones) {
        int size = stones.length;
        Queue<Integer> heap = new PriorityQueue<>(size,new Comparator<Integer>(){
            @Override
            public int compare(Integer i1,Integer i2){
                return i2-i1;
            }
        });
        for (int i : stones) {
            heap.offer(i);
        }
        while(heap.size()>1){
            int y = heap.poll();
            int x = heap.poll();
            if(x!=y){
                heap.offer(y-x);
            }
        }
        if(heap.size()==1) return heap.peek();
        return 0;
    }
}

时间:$O(n*logn)$ 空间:$O(n)$