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

[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{}{
    out := *h
    x := out[len(out)-1]
    *h = out[:len(out)-1]
    return x
}

func lastStoneWeight(stones []int) int {
    h := &hp{}
    for i:=0;i<len(stones);i++{
        heap.Push(h,stones[i])
    }
    for h.Len() > 1{
        x := heap.Pop(h).(int)
        y := heap.Pop(h).(int)
        if x > y{
            heap.Push(h,x-y)
        }
    }
    if h.Len()>0{
        return heap.Pop(h).(int)
    }
    return 0
}

[ZacheryCao]

Idea

Heap

Code

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

Complexity:

Time: O(N log N). Heap pop and heap push is O(log N). We need to go through all arrays for each simulation. Space: O(N)

[yingliucreates]

link:

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

代码 Javascript

function PriorityQueue() {
  this.heap = [null];
  this.insert = function (value) {
    this.heap.push(value);
    let currentNodeIdx = this.heap.length - 1;
    let currentNodeParentIdx = Math.floor(currentNodeIdx / 2);
    while (
      this.heap[currentNodeParentIdx] &&
      value > this.heap[currentNodeParentIdx]
    ) {
      let parent = this.heap[currentNodeParentIdx];
      this.heap[currentNodeParentIdx] = value;
      this.heap[currentNodeIdx] = parent;
      currentNodeIdx = currentNodeParentIdx;
      currentNodeParentIdx = Math.floor(currentNodeIdx / 2);
    }
  };

  this.remove = function () {
    if (this.heap.length < 3) {
      const toReturn = this.heap.pop();
      this.heap[0] = null;
      return toReturn;
    }
    const toRemove = this.heap[1];
    this.heap[1] = this.heap.pop();
    let currentIdx = 1;
    let [left, right] = [2 * currentIdx, 2 * currentIdx + 1];
    let currentChildIdx =
      this.heap[right] && this.heap[right] >= this.heap[left] ? right : left;
    while (
      this.heap[currentChildIdx] &&
      this.heap[currentIdx] < this.heap[currentChildIdx]
    ) {
      let currentNode = this.heap[currentIdx];
      let currentChildNode = this.heap[currentChildIdx];
      this.heap[currentChildIdx] = currentNode;
      this.heap[currentIdx] = currentChildNode;
      currentIdx = currentChildIdx;
      [left, right] = [2 * currentIdx, 2 * currentIdx + 1];
      currentChildIdx =
        this.heap[right] && this.heap[right] >= this.heap[left] ? right : left;
    }
    return toRemove;
  };
}

const lastStoneWeight = function (stones) {
  const pq = new PriorityQueue();
  for (let i = 0; i < stones.length; i++) {
    pq.insert(stones[i]);
  }
  while (pq.heap.length > 2) {
    let x = pq.remove();
    let y = pq.remove();
    if (x != y) {
      let max = Math.max(x, y);
      let min = Math.min(x, y);
      let z = max - min;
      pq.insert(z);
    }
  }
  return pq.remove();
};

[bingyingchu]

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

        while len(heap) > 1:
            big1 = abs(heapq.heappop(heap))
            big2 = abs(heapq.heappop(heap))
            heapq.heappush(heap, -(big1-big2))

        if len(heap) == 1:
            return abs(heapq.heappop(heap))

        return 0

Time/Space: O(n)

[okbug]

var lastStoneWeight = function(stones) {
    while(stones.length > 1) {
        stones.sort((a, b) => a - b);
        let a = stones.pop();
        let b = stones.pop();
        if(a !== b) stones.push(a - b);
    }
    return stones[0] || 0
};

[user1689]

题目

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

思路

Heap

python3

class heapq:

    def __init__(self, descend = False):
        self.heap = []
        self.descend = descend

    def _swap(self, idx1, idx2):
        self.heap[idx1], self.heap[idx2] = self.heap[idx2], self.heap[idx1]

    def _smaller(self, lst, rst):
        return lst > rst if self.descend else lst < rst

    def _size(self):
        return len(self.heap)

    def _top(self):
        if self.heap:
            return self.heap[0]
        return None

    def _push(self, x):
        self.heap.append(x)
        self._sift_up(self._size() - 1)

    def _pop(self):
        tmp = self.heap[0]
        self._swap(0, self._size() - 1)
        self.heap.pop()
        self._sift_down(0)
        return tmp

    def _sift_up(self, idx):
        while (idx != 0):
            parentIdx = (idx - 1) // 2

            if (self._smaller(self.heap[parentIdx], self.heap[idx])):
                break

            self._swap(parentIdx, idx)

            idx = parentIdx

    def _sift_down(self, idx):
        while (idx*2+1 < self._size()):
            smallestIdx = idx
            leftIdx = idx*2+1
            rightIdx = idx*2+2

            if (self._smaller(self.heap[leftIdx], self.heap[idx])):
                smallestIdx = leftIdx

            if (rightIdx < self._size() and self._smaller(self.heap[rightIdx], self.heap[smallestIdx])):
                smallestIdx = rightIdx

            if (smallestIdx == idx):
                break

            self._swap(smallestIdx, idx)
            idx = smallestIdx

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        heap = heapq(descend = True)
        for s in stones:
            heap._push(s)

        while(heap._size() > 1):
            y = heap._pop()
            x = heap._pop()
            if y != x:
                heap._push(y - x)

        if heap._size() >= 1:
            return heap._top()
        return 0

复杂度分析

• time nlogn
• space n

相关题目

1. 待补充

[wenjialu]

idea

由每次取出最重的石头比较，想到需要排序。 由插入删除的时间复杂度，想到堆。

code

class Solution:
    要从大顶堆里面选出最重的。小顶堆的话就没办法取出最大的了。所以加个负号，就能让绝对值最大的变堆顶。
    def lastStoneWeight(self, stones: List[int]) -> int:
        stones_heap = [-stone for stone in stones]
        heapq.heapify(stones_heap)
        # print(stones_heap)
        while len(stones_heap) >= 2:
            s1, s2 = heapq.heappop(stones_heap), heapq.heappop(stones_heap) #s1<s2
            # print(s1,s2)
            if s1 != s2:
               heapq.heappush(stones_heap, s1 - s2) # a - b < 0       
        return -stones_heap[-1] if stones_heap else 0 

complexity

time：O(NlogN) space: O(N)

[Laurence-try]

思路

heap

代码

使用语言：Python3

import heapq
class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        for i in range(len(stones)):
            stones[i] *= -1
        heapq.heapify(stones)
        while len(stones) > 1:
            stone_1 = heapq.heappop(stones)
            stone_2 = heapq.heappop(stones)
            if stone_1 != stone_2:
                heapq.heappush(stones, stone_1 - stone_2)

        return -heapq.heappop(stones) if stones else 0

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

[kennyxcao]

1046. Last Stone Weight

Intuition

• Heap

Code

/**
 * @param {number[]} stones
 * @return {number}
 */
const lastStoneWeight = function(stones) {
  const maxHeap = new BinaryHeap((c, p) => c < p);
  stones.forEach((stone) => maxHeap.push(stone));
  while (maxHeap.size() > 1) {
    const diff = maxHeap.pop() - maxHeap.pop();
    if (diff > 0) {
      maxHeap.push(diff);
    }
  }
  return maxHeap.size() ? maxHeap.pop() : 0;
};

Complexity Analysis

• Time: O(nlogn)
• Space: O(n)

[RocJeMaintiendrai]

代码

class Solution {
    public int lastStoneWeight(int[] stones) {
        Queue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
        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();
    }
}

复杂度分析

时间复杂度

O(nlogn)

空间复杂度

O(n)

[Francis-xsc]

思路

优先队列

代码

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)，其中 N 为数组长度。
• 空间复杂度：O(N)

[ai2095]

1046. Last Stone Weight

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

Topics

-Heap

思路

Heap

代码 Python

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

复杂度分析

时间复杂度： O(N*Log(N))
空间复杂度： O(N)

[ymkymk]

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

[tongxw]

思路

设置一个大顶堆，所有数字入堆，然后从堆内取出最大的两个数字，把它们的差再放入堆中，直到堆内剩下的数字少于2个。最后如果堆不为空就返回堆顶，否则返回0。

代码

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

        while (heap.size() > 1) {
            int stone1 = heap.poll();
            int stone2 = heap.poll();
            if (stone1 != stone2) {
                heap.offer(stone1 - stone2);
            } 
        }

        return heap.isEmpty() ? 0 : heap.peek();
    }
}

TC: O(nlogn) SC: O(n)

[kidexp]

thoughts

heap 把stones数组的值取反加入heap 然后pop 出两两比较 知道最后元素个数<=1

code

import heapq

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        heap = []
        for stone in stones:
            heapq.heappush(heap, -stone)
        while len(heap) > 1:
            x, y = heapq.heappop(heap), heapq.heappop(heap)
            if x == y:
                continue
            else:
                heapq.heappush(heap, x-y)
        return -heap[0] if heap else 0

complexity

Time O(nlgn)

Space O(n)

[zjsuper]

Time O(NlogN)

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

[itsjacob]

Intuition

• [tags] max heap

Implementation

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
      std::make_heap(stones.begin(), stones.end());
      while (stones.size() > 1) {
        auto stone1 = stones.front();
        std::pop_heap(stones.begin(), stones.end());
        stones.pop_back();
        auto stone2 = stones.front();
        std::pop_heap(stones.begin(), stones.end());
        stones.pop_back();
        if (stone1 != stone2) {
          stones.push_back(stone1 - stone2);
          std::push_heap(stones.begin(), stones.end());
        }
      }
      int res{0};
      if (!stones.empty()) {
        res = stones.front();
      }
      return res;
    }
};

Complexity

• Time complexity: O(NlogN)
• Space complexity: O(N)

[15691894985]

【Day 86】1046.最后一块石头的重量

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

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        heap = []
        for num in stones:
            heapq.heappush(heap,-num)
        while len(heap)>1: 
            left = heapq.heappop(heap)
            right = heapq.heappop(heap)
            if left != right:
                 heapq.heappush(heap,left-right)
        if heap:  return -heap[0]                 
        return 0

复杂度分析：

时间复杂度：O(nlogn)

空间复杂度：O（n）

[Yufanzh]

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        #max heap
        #since default python heap is min heap, use negative value to realize max heap
        h = [-stone for stone in stones]
        heapq.heapify(h)

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

        if len(h) > 0:
            return -h[0]
        else:
            return 0

Complexity Analysis

• Time complexity: O(NlogN)
• Space complexity: O(N)

[Moin-Jer]

思路

---

最大堆

代码

---

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)

[falconruo]

思路: 要求每次取最大的两块石头，考虑使用大顶堆排序，每次取堆顶的两块石头，如果重量不相等则把差入堆

最后堆里右两种情况：1. 为空 2.剩下唯一的一块

复杂度分析：

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

代码（C++）：

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        int n = stones.size();

        if (n <= 1) return stones[0];

        // MaxHeap
        priority_queue<int> pq;

        for (auto stone : stones)
            pq.push(stone);

        while (!pq.empty() && pq.size() != 1) {
            int s1 = pq.top();
            pq.pop();
            int s2 = pq.top();
            pq.pop();

            if (s1 != s2)
                pq.push(s1 - s2);
        }

        return pq.empty() ? 0 : pq.top();
    }
};

[asterqian]

思路

max heap

代码

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq; // max heap
        for (int i = 0; i < stones.size(); ++i) {
            pq.push(stones[i]);
        }
        while (pq.size() >= 2) {
            int x = pq.top();
            pq.pop();
            int y = pq.top();
            pq.pop();
            if (x != y) {
                pq.push(x - y); // max heap so x must be bigger than y
            }
        }
        return pq.size() == 0 ? 0 : pq.top();
    }
};

时间复杂度 O(nlogn)

空间复杂度 O(n)

[Zhi22]

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

[learning-go123]

思路

• 队排序

代码

• 语言支持：Go

Go Code:

type maxPriorityQueue []int
func (pq *maxPriorityQueue) Len() int { return len(*pq) }
func (pq maxPriorityQueue) Less(i, j int) bool  { return pq[i] > pq[j] }
func (pq maxPriorityQueue) Swap(i, j int)       { pq[i], pq[j] = pq[j], pq[i] }
func (pq *maxPriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(int)) }
func (pq *maxPriorityQueue) Pop() interface{} {
    res := (*pq)[len(*pq)-1]
    *pq = (*pq)[:len(*pq)-1]
    return res
}

func lastStoneWeight(stones []int) int {
    pq := &maxPriorityQueue{}
    heap.Init(pq)
    for _, v := range stones {
        heap.Push(pq, v)
    }
    for pq.Len() > 1 {
        a := heap.Pop(pq).(int)
        b := heap.Pop(pq).(int)
        if a != b {
            heap.Push(pq, a-b)
        }
    }
    if pq.Len() == 0 {
        return 0
    }
    return heap.Pop(pq).(int)
}

复杂度分析

令 n 为数组长度。

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

[aduispace]

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

[zhiyuanpeng]

 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]

[jiahui-z]

思路: heap

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 heaviestStone = maxHeap.poll();
            int secondHeaviestStone = maxHeap.poll();
            if (secondHeaviestStone < heaviestStone) {
                maxHeap.offer(heaviestStone - secondHeaviestStone);
            }
        }

        return maxHeap.isEmpty() ? 0 : maxHeap.peek();
    }
}

Time Complexity: O(nlogn) Space Complexity: O(n)

[muimi]

思路

优先队列

代码

class Solution {
  public int lastStoneWeight(int[] stones) {
    PriorityQueue<Integer> 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();
      pq.offer(a - b);
    }
    return pq.poll();
  }
}

复杂度

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

[florenzliu]

Explanation

• heap-based simulation

Code

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

        for i in range(len(stones)):
            stones[i] *= -1

        heapq.heapify(stones)

        while len(stones) > 1:
            stone_1 = heapq.heappop(stones)
            stone_2 = heapq.heappop(stones)
            if stone_1 != stone_2:
                heapq.heappush(stones, stone_1 - stone_2)
        return -heapq.heappop(stones) if stones else 0

Time: O(nlogn)

Space: O(n)

[Bingbinxu]

思路 topK的变形，利用topK维持一个从大到小的队列，然后比较选择粉碎或者加入 代码(C++)

实现语言: C++
class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        if(stones.size() == 1) return stones.front();
        priority_queue<int> topk;
        for(auto& i : stones)
        {
            topk.push(i);
        }
        while(topk.size()>=2)
        {
            int fs = topk.top();
            topk.pop();
            int ss = topk.top();
            topk.pop();
            if(fs != ss)
            {
                topk.push(fs - ss);
            }
        }
        return topk.empty() ? 0 : topk.top();
    }
};

复杂度分析 时间复杂度: O(NlogN) 空间复杂度: O(N）

[hellowxwworld]

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

[weichuliao]

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

[chaggle]

---

title: "Day 86 1046. 最后一块石头的重量" date: 2021-12-04T17:42:18+08:00 tags: ["Leetcode", "c++", "heap"] categories: ["91-day-algorithm"] draft: true

---

1046. 最后一块石头的重量

题目

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

每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 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

题目思路

• 1、今日仍为最大堆的使用办法，拒绝使用库函数自己写。

class Solution {
public:
    void buildmaxheap(vector<int>& stones, int i, int n) {
        int p = stones[i];
        for (int j = 2 * i + 1; j < n; j = 2 * j + 1) 
        {
            if (j < n - 1 && stones[j] < stones[j + 1]) j++;
            if (p >= stones[j]) break;
            else 
            {
                stones[i] = stones[j];
                i = j;
            }
        }
        stones[i] = p;
    }

    int lastStoneWeight(vector<int>& stones) {
        int max1, max2;
        int n = stones.size();
        for (int i = (n - 1) / 2; i >= 0; i--) buildmaxheap(stones, i, n);
        while (n > 1)
        {
            max1 = stones[0];
            stones[0] = stones[--n];
            buildmaxheap(stones, 0, n);
            max2 = stones[0];
            if (max1 == max2)
            {
                if(n < 2) return 0;
                else stones[0] = stones[--n];
            }
            else stones[0] = abs(max1 - max2);
            buildmaxheap(stones, 0, n);
        }
        return stones[0];
    }
};

复杂度

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

[chen445]

代码

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        new_stones=[-1*stone for stone in stones]
        heapq.heapify(new_stones)
        while len(new_stones) >1:
            y=heapq.heappop(new_stones)
            x=heapq.heappop(new_stones)
            if y !=x:
                heapq.heappush(new_stones,y-x)
        if new_stones:
            return -new_stones[0]
        else:
            return 0

复杂度

Time: O(nlogn)

Space: O(n)

[JinhMa]

class Solution { public int lastStoneWeight(int[] stones) { if (stones.length == 2) { return Math.abs(stones[0] - stones[1]); } if (stones.length == 1) { return stones[0]; } Arrays.sort(stones); if (stones[stones.length - 3] == 0) { return stones[stones.length - 1] - stones[stones.length - 2]; } stones[stones.length - 1] = stones[stones.length - 1] - stones[stones.length - 2]; stones[stones.length - 2] = 0; return lastStoneWeight(stones); } }

[L-SUI]

/**

• @param {number[]} stones
• @return {number} */ var lastStoneWeight = function(stones) { if (stones.length == 1) { // 如果数组长度为 1 直接返回 return stones[0]; } while (stones.length > 1) { // 数组长度大于 1，循环 let nowMaxNum = Math.max(...stones) // 获取当前数组最大值 let maxNumIndex = stones.indexOf(nowMaxNum) // 获取最大值的索引 stones.splice(maxNumIndex, 1) // 删除最大值 let secondMaxNum = Math.max(...stones) // 继续获取数组最大值，这时候对于这轮来说是第二大的值 let secondNumIndex = stones.indexOf(secondMaxNum) // 获取索引 let reduceValue = nowMaxNum - secondMaxNum // 求差 if (reduceValue > 0) { // 如果差值大于0，则删除当前最大值，并且插入插值 stones.splice(secondNumIndex, 1, reduceValue) } else { // 否者删除当前最大值 stones.splice(secondNumIndex, 1) } } return stones.length ? stones[0] : 0 };

[wangyifan2018]

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