【Day 86 】2021-12-04 - 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

[yanglr]

思路:

读完题, 发现是 top K问题的变形, 于是可以使用堆(优先队列) 求解。

首先特判一下, 如果原数组的size == 1, 可以直接取出数组的第一个元素返回即可。

否则, 将数组中的数都放进一个大顶堆pq中, 使用一个while循环, 只要pq的size >= 2, 就每次从top位置取出两个数 firstBig 和 secondBig:

• 如果 firstBig = secondBig, 就继续
• 如果 firstBig ≠ secondBig, 就把 first-second 这个值再压入p。

如果循环结束时, pq为空则返回0, 否则pq的顶部元素即为所求。

代码:

实现语言: C++

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        if (stones.size() == 1) return stones.front();
        priority_queue<int> pq;
        for (auto& s : stones)
            pq.push(s);
        while (pq.size() >= 2) /* 别漏了==的情况 */
        {
            int firstBig = pq.top();
            pq.pop();
            int secondBig = pq.top();
            pq.pop();
            if (firstBig != secondBig)
                pq.push(firstBig - secondBig);
        }
        return pq.empty() ? 0 : pq.top();
    }
};

复杂度分析

• 时间复杂度: O(N logN)
• 空间复杂度: O(N)

[joeytor]

思路

使用堆的方法

先构建一个最大堆

每次如果堆中元素多于两个, 那么取出堆顶的两个元素, 并计算 remain, 如果 remain 不为 0, 将 remain 加入堆中继续循环

最后返回 堆顶元素如果 h 中还有元素 (代表还有一个元素), 否则返回 0, 代表没有元素剩余

import heapq
class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        h = [-x for x in stones]
        heapq.heapify(h)
        while len(h) >= 2:
            s1 = heapq.heappop(h)
            s2 = heapq.heappop(h)
            remain = -s1 - (-s2)
            if remain != 0:
                heapq.heappush(h, -remain)
        return 0 if not h else -h[0]

复杂度

时间复杂度: O(nlogn) 每次从堆中取出元素需要 O(logn) 的时间, 一共需要进行 O(n) 次

空间复杂度: O(n) 堆的空间复杂度

[chenming-cao]

解题思路

堆。模拟整个流程。建立大顶堆，将所有石头放入堆中，如果堆中石头多于2个，则拿出最大的两个进行粉碎，直到最后剩小于2个石头为止。

代码

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);
        // put stones into max-heap
        for (int stone : stones) {
            heap.offer(stone);
        }
        // simulate the smash process
        while (heap.size() >= 2) {
            int y = heap.poll();
            int x = heap.poll();
            if (x != y) {
                heap.offer(y - x);
            }
        }
        return heap.size() == 0 ? 0 : heap.poll();
    }
}

复杂度分析

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

[biancaone]

    def lastStoneWeight(self, stones: List[int]) -> int:
        q = [-stone for stone in stones]
        heapq.heapify(q)
        while (len(q)) > 1:
            heapq.heappush(q, heapq.heappop(q) - heapq.heappop(q))
        return -q[0]

[chakochako]

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

[ginnydyy]

Problem

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

Note

• heap

Solution

class Solution {
    public int lastStoneWeight(int[] stones) {
        if(stones == null || stones.length == 0){
            return 0;
        }
        
        int n = stones.length;
        PriorityQueue<Integer> q = new PriorityQueue<>(n, Collections.reverseOrder());
        
        for(int i = 0; i < stones.length; i++){
            q.offer(stones[i]);
        }
        
        while(q.size() > 1){
            int s1 = q.poll();
            int s2 = q.poll();
            if(s1 != s2){
                q.offer(s1 - s2);
            }
        }
        
        return q.isEmpty()? 0: q.poll();
    }
}

Complexity

• T: O(nlogn). n is the length of stones array. O(logn) for each offer and poll operation, for n stones, it requires n operations. Overall O(nlogn).
• S: O(n) for the priority queue.

[zhangzz2015]

思路

• 题目的关键是能快速找到最大和次大的石头，另外要修改石头重量再重新排序，heap是比较适合的数据结构，使用大顶堆，每次推出最大和次大，把非0的difference再次放入heap。时间复杂度为O(n logn) 空间复杂度为 O(n)

关键点

代码

• 语言支持：C++

C++ Code:

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

[pophy]

思路

• PQ模拟

Java Code

    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> (b - a));
        for (int n : stones) {
            pq.add(n);
        }
        while (pq.size() > 1) {
            int stone1 = pq.poll();
            int stone2 = pq.poll();            
            if (stone1 != stone2) {
                pq.add(Math.abs(stone1 - stone2));
            }
        }
        return pq.isEmpty() ? 0 : pq.poll();
    }

时间&空间

• 时间 O(nlog(n))
• 空间 O(n)

[laofuWF]

# use min heap
# time: O(NlogN)
# space: O(N)

import heapq

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        if len(stones) == 1:
            return stones[0]
        # min heap
        heap = []
        for stone in stones:
            heapq.heappush(heap, -stone)
        
        while len(heap) > 1:
            candidate1 = -heapq.heappop(heap)
            candidate2 = -heapq.heappop(heap)
            
            if candidate1 == candidate2:
                if not heap: return 0
                continue
            left = abs(candidate1 - candidate2)
            heapq.heappush(heap, -left)
        
        return -heapq.heappop(heap)

[akxuan]

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        stones.sort()
        
     
        while len(stones)> 1:
            a = stones.pop()
            b = stones.pop()
            stones.append(abs(a-b))
            stones.sort()
            
        
        if stones:
            return stones[0]
        else:
            return 0 
        

[Daniel-Zheng]

思路

堆。

代码(C++)

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();
    }
};

复杂度分析

• 时间复杂度：O(NLogN)
• 空间复杂度：O(N)

[mannnn6]

代码

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)

[LAGRANGIST]

class Solution {
public:
int lastStoneWeight(vector& stones) {
priority_queue 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();
}
};