You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

1046. 最后一块石头的重量 - Last Stone Weight

. 1 min read

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/last-stone-weight/


Analysis

关键点在于每次都能拿到最重的,并且执行过程中可能产生新的较轻的石头。
因此采用优先队列完成(大顶堆)

Solution 【大顶堆】 ( 5ms)

执行用时 : 5 ms, 在Last Stone Weight的Java提交中击败了43.52% 的用户
内存消耗 : 34 MB, 在Last Stone Weight的Java提交中击败了100.00% 的用户

class Solution {
    public int lastStoneWeight(int[] stones) {
        /* 使用优先对列保证每次能拿到最大的数 */
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @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();
    }
}

复杂度分析

时间:$O(NlogN)$
空间:$O(N)$

Analysis

这个思路在于每次都重新排序,
理论上复杂度会更高,但实际更快
是因为每次最多只有一对元素逆序吗。。。

Solution【排序】 ( 1ms)

class Solution {
    public int lastStoneWeight(int[] stones) {
        int end = stones.length - 1;
        int k = 0;
        while( k != stones.length && k != stones.length - 1 ){
            Arrays.sort(stones);
            int x = stones[end - 1];
            int y = stones[end];
            if( x == y ){
                stones[end - 1] = stones[end] = -1;
                //end -= 2;
                k += 2;
            }else{
                stones[end - 1] = stones[end] - stones[end - 1];
                stones[end] = -1;
                k += 1;
            }
        }
        Arrays.sort(stones);
        return k == stones.length ? 0 : stones[end];
    }
}