LeetCode 1046. 最后一块石头的重量

Categories:

题目描述
思路分析
1. 解法一：大顶堆模拟（推荐）
相似题目

题目描述

✅ 1046. 最后一块石头的重量

思路分析

解法一：大顶堆模拟（推荐）

核心思路：

每次取出最重的两块石头进行碰撞。

若质量不同，剩余差值重新放回堆中。

直到堆中石头数不超过 1。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示石头数量。

空间复杂度：O(n)，堆存储石头重量。

import java.util.*;

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        for (int s : stones) {
            heap.offer(s);
        }

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

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

import "container/heap"

type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func lastStoneWeight(stones []int) int {
    h := &MaxHeap{}
    heap.Init(h)
    for _, s := range stones {
        heap.Push(h, s)
    }

    for h.Len() > 1 {
        a := heap.Pop(h).(int)
        b := heap.Pop(h).(int)
        if a != b {
            heap.Push(h, a-b)
        }
    }

    if h.Len() == 0 {
        return 0
    }
    return heap.Pop(h).(int)
}

相似题目

题目	难度	考察点
215. 数组中的第 K 个最大元素	中等	堆
347. 前 K 个高频元素	中等	堆
973. 最接近原点的 K 个点	中等	堆
1046. 最后一块石头的重量	简单	堆模拟
703. 数据流中的第 K 大元素	简单	堆

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/45215791