1046. Last Stone Weight

題目描述

• 有一堆石頭，每塊石頭的重量都是正整數。
• 每次挑出兩塊最重的石頭，互相撞擊：
  • 如果兩塊石頭的重量相等，它們會同時粉碎消失；
  • 如果兩塊石頭的重量不相等，則剩下較重的那塊重量變為兩塊石頭重量之差。
• 不斷重複此操作直到剩下一塊或沒有石頭為止。
• 問最後剩下的石頭重量是多少（如果沒有剩下石頭，返回0）。

解題思路

• 本題的核心在於每次都要找出兩塊最重的石頭進行處理，使用「堆」結構（Heap）來解題會非常高效，因為它能快速找到最大值和次大值。
• Python 的 heapq 模組是一個最小堆（Min-Heap），因此需要將所有石頭的重量取負值來模擬最大堆（Max-Heap）。

解題步驟

1. 將所有石頭的重量取負數：
   • 這是因為 Python 的 heapq 模組默認是最小堆，而題目需要的是最大堆。取負後可以在取出元素時先轉換回正數，模擬最大堆的行為。
2. 建立堆結構：
   • 使用 heapq.heapify() 將負值石頭列表轉換成堆結構。
3. 模擬石頭撞擊過程：
   • 從堆中取出兩個最重的石頭（注意要先轉換回正數），比較重量：
     • 如果重量相等，則這兩塊石頭都會消失。
     • 如果重量不相等，將較重石頭的重量減去較輕石頭的重量，結果重新放回堆中。
4. 返回結果：
   • 重複上述過程直到堆中剩下一塊或沒有石頭。若堆中還有石頭，返回其重量（注意轉回正數）；如果沒有石頭，則返回0。

import heapq

def lastStoneWeight(stones):
    # 1. 將石頭重量取負數，轉換為最大堆
    stones = [-stone for stone in stones]
    heapq.heapify(stones)

    # 2. 重複撞擊石頭直到剩下最多一塊
    while len(stones) > 1:
        # 取出兩塊最重的石頭
        stone1 = -heapq.heappop(stones)
        stone2 = -heapq.heappop(stones)
        
        # 如果兩塊石頭不相等，將剩下的重量放回堆中
        if stone1 != stone2:
            heapq.heappush(stones, -(stone1 - stone2))

    # 3. 返回最終剩餘的石頭重量（若無剩餘則返回0）
    return -stones[0] if stones else 0

複雜度

時間複雜度：

• O(N log N)：最初建立堆的操作是 O(N)，每次取出最大值並重新插入的操作是 O(log N)。在最壞情況下，可能需要進行 N 次操作，因此最終時間複雜度為 O(N log N)。
  空間複雜度：
• O(N)：需要用到一個堆結構來存放石頭，因此空間複雜度為 O(N)。

思路擴展

本題可以視作「模擬撞擊過程並持續保持最大值」的問題，因此也可以用其他方式如排序、暴力解法來實現，但時間複雜度和效率都不如使用堆結構。