Khối Lượng Viên Đá Cuối Cùng (Last Stone Weight) Trong Python

Cho mảng stones trọng lượng viên đá. Lặp: lấy 2 viên nặng nhất x ≤ y:

• Nếu x == y: cả 2 vỡ
• Nếu x != y: viên x vỡ, viên y còn y - x

Trả về trọng lượng viên cuối (0 nếu không còn).

Ví dụ: [2,7,4,1,8,1] → 7&8→1, mảng [2,4,1,1,1] → 2&4→2, [2,1,1,1] → 2&1→1, [1,1,1] → 1&1 vỡ, [1] → kết quả 1.

Thuật toán Heap (Tối ưu)

Dùng Max Heap (Python heapq là min-heap → lưu giá trị âm).

import heapq

class Solution(object):
    def lastStoneWeight(self, stones):
        # Max heap: lưu giá trị âm
        max_heap = [-s for s in stones]
        heapq.heapify(max_heap)
        
        while len(max_heap) > 1:
            y = -heapq.heappop(max_heap)  # nặng nhất
            x = -heapq.heappop(max_heap)  # nặng thứ 2
            if x != y:
                heapq.heappush(max_heap, -(y - x))
        
        return -max_heap[0] if max_heap else 0

ob1 = Solution()
print(ob1.lastStoneWeight([2,7,4,1,8,1]))  # 1
print(ob1.lastStoneWeight([1,2,3,4,5]))    # 1

Cách đơn giản (Sort mỗi vòng - O(n² log n))

def lastStoneWeight_simple(stones):
    while len(stones) > 1:
        stones.sort()
        y = stones.pop()
        x = stones.pop()
        if x != y:
            stones.append(y - x)
    return stones[0] if stones else 0

Độ phức tạp

• Heap: O(n log n) time, O(n) space
• Sort mỗi vòng: O(n² log n) time, O(1) space

Đầu vào / Đầu ra

Input:  [2,7,4,1,8,1]
Output: 1