GuilinDev

Lc1046

05 August 2008

1046 Last Stone Weight

题目

We have a collection of stones, each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights 

1

x
and 
1

y
with 
1

x <= y
. The result of this smash is:

  • If 
    1

    x == y
    , both stones are totally destroyed;
  • If 
    1

    x != y
    , the stone of weight 
    1

    x
    is totally destroyed, and the stone of weight 
    1

    y
    has new weight 
    1

    y-x
    .

At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.)

Example 1:

1
2
3
4
5
6
7

Input: [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 last stone.

Note:

  1. 1

    1 <= stones.length <= 30

  2. 1

    1 <= stones[i] <= 1000

分析

用优先队列来模拟一个大顶堆，每次取最大的两个数相减，然后把相减的数再返回队列。O(NLogN)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13

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 temp = pq.poll() - pq.poll();
            pq.offer(temp);
        }
        return pq.poll(); //这里允许0进入堆中，最后返回
    }
}
This site is open source. Improve this page.