Last Stone Weight: minh họa đơn giản nhất của heap

Chọn hai viên đá nặng nhất, đập vào nhau, bỏ phần dư lại vào đống. Lặp đến khi còn tối đa một viên. Đó là toàn bộ bài toán — và nó đọc như một định nghĩa giáo khoa cho câu hỏi "khi nào dùng heap." Đây là bài luyện tập thực tế đầu tiên trong series heap-priority-queue: không phải vì khó, mà vì nó buộc bạn phải nói rõ tại sao heap là công cụ đúng và các lựa chọn khác tốn kém bao nhiêu.

Constraints thực sự nói gì

1 <= stones.length <= 30. Ba mươi viên đá. Nhỏ đến mức một vòng lặp O(n²) chạy dưới một microsecond. Constraint này không bắt buộc bạn tìm giải pháp tối ưu vì hiệu năng — ở n=30, ngay cả bubble sort cũng tức thì. Điều nó cho bạn biết là sắp xếp toàn bộ danh sách mỗi vòng không phải thảm họa ở đây. Nó hoạt động được. Câu hỏi là liệu nó có phải cách tiếp cận rõ ràng hơn không.

1 <= stones[i] <= 1000. Mọi trọng lượng đều dương. Điều này quan trọng vì một lý do tinh tế: khi bạn tính y - x sau khi đập, kết quả đảm bảo không âm, nên bạn không bao giờ đưa số không hoặc âm trở lại tập hợp. Invariant của heap giữ sạch — mỗi phần tử trong heap là trọng lượng đá hợp lệ.

Constraint ngầm mà không ai ghi ra: bạn cần hai phần tử lớn nhất lặp đi lặp lại, và sau mỗi lần rút tập hợp thay đổi. Đó chính xác là hình dạng của bài toán heap. Không phải "tìm max một lần" (dùng max() thôi), không phải "sắp xếp một lần rồi xử lý theo thứ tự" (đó là stack hay two-pointer), mà là "duy trì quyền truy cập động vào max khi phần tử được thêm và xóa."

Brute force: sắp xếp mỗi vòng

Mô phỏng trực tiếp: trước mỗi lần đập, sắp xếp danh sách, lấy hai phần tử cuối, tính phần dư, thêm lại nếu khác không, lặp lại.

class Solution:
    def lastStoneWeight(self, stones: list[int]) -> int:
        while len(stones) > 1:
            stones.sort()
            y = stones.pop()  # nặng nhất
            x = stones.pop()  # nặng thứ hai
            if y != x:
                stones.append(y - x)
        return stones[0] if stones else 0

public class Solution {
    public int LastStoneWeight(int[] stones) {
        var list = new List<int>(stones);
        while (list.Count > 1) {
            list.Sort();
            int y = list[list.Count - 1];
            int x = list[list.Count - 2];
            list.RemoveAt(list.Count - 1);
            list.RemoveAt(list.Count - 1);
            if (y != x) list.Add(y - x);
        }
        return list.Count > 0 ? list[0] : 0;
    }
}

Time: O(n² log n). Mỗi vòng lặp sort tốn O(n log n), và bạn có thể có tới n vòng lặp (mỗi lần đập giảm số đá ít nhất một, đôi khi hai). Space: O(1) phụ, vì sort in-place.

Ở n=30 hoàn toàn ổn. Trong interview tôi thường viết cái này trước để có gì đó đúng trên bảng nhanh chóng, rồi giải thích tại sao phiên bản heap sạch hơn nếu constraint tăng. Cách sắp xếp có một ưu điểm: không cần kiến thức heap và rõ ràng là đúng.

Vấn đề ở quy mô lớn là sự lãng phí. Bạn đang sắp xếp toàn bộ danh sách còn lại để tìm hai phần tử. Hầu hết thứ tự đó là thông tin bạn lập tức bỏ đi — sau lần đập, bạn cần max mới, không phải danh sách đã sắp xếp đầy đủ.

Max-heap: O(n log n)

Một max-heap cho bạn phần tử lớn nhất trong O(1) peek và xóa nó trong O(log n). Build từ n phần tử tốn O(n). Vòng lặp chạy tối đa n lần (mỗi lần đập xóa ít nhất một đá), mỗi vòng làm hai lần rút O(log n) và tối đa một lần chèn O(log n). Tổng: O(n log n).

heapq của Python là min-heap. Trick chuẩn là phủ định giá trị trước khi chèn, rồi phủ định lại khi rút.

import heapq
 
class Solution:
    def lastStoneWeight(self, stones: list[int]) -> int:
        heap = [-s for s in stones]
        heapq.heapify(heap)
 
        while len(heap) > 1:
            y = -heapq.heappop(heap)
            x = -heapq.heappop(heap)
            if y != x:
                heapq.heappush(heap, -(y - x))
 
        return -heap[0] if heap else 0

C# có PriorityQueue<TElement, TPriority> (từ .NET 6). Nó là min-heap theo giá trị priority. Truyền -stone làm priority để đảo thứ tự.

public class Solution {
    public int LastStoneWeight(int[] stones) {
        var pq = new PriorityQueue<int, int>();
        foreach (int s in stones)
            pq.Enqueue(s, -s);
 
        while (pq.Count > 1) {
            int y = pq.Dequeue();
            int x = pq.Dequeue();
            if (y != x)
                pq.Enqueue(y - x, -(y - x));
        }
 
        return pq.Count > 0 ? pq.Peek() : 0;
    }
}

Space: O(n) cho heap. Bạn đổi O(n) space lấy việc giảm từ O(n² log n) xuống O(n log n). Ở n=30 sự đánh đổi này không quan trọng; ở n=10⁶ thì đó là khác biệt giữa nhanh và chạy được.

Trace từng bước: [2, 7, 4, 1, 8, 1]

Output mong đợi là 1. Đây là quá trình với phiên bản heap:

Vòng 1: rút 8 và 7. 8 - 7 = 1. Thêm 1 vào heap. Heap thành [4, 2, 1, 1, 1].

Vòng 2: rút 4 và 2. 4 - 2 = 2. Thêm 2. Heap: [2, 1, 1, 1].

Vòng 3: rút 2 và 1. 2 - 1 = 1. Thêm 1. Heap: [1, 1, 1].

Vòng 4: rút 1 và 1. Bằng nhau, cả hai bị hủy. Không thêm gì. Heap: [1].

Còn một phần tử. Return 1. Khớp output mong đợi.

Edge case

Một viên đá (stones = [1]): điều kiện while len > 1 sai ngay từ đầu. Heap có một phần tử; trả về nó. Không có gì phức tạp.

Hai viên bằng nhau (stones = [3, 3]): cả hai bị hủy trong một vòng. Heap rỗng sau khi pop. return heap[0] if heap else 0 trả về 0. Đây là trường hợp duy nhất có thể trả về 0.

Tất cả bằng nhau, số chẵn (stones = [2, 2, 2, 2]): các cặp triệt tiêu nhau. Heap hoàn toàn rỗng. Return 0.

Tất cả bằng nhau, số lẻ (stones = [2, 2, 2]): hai cái hủy nhau, một cái còn lại. Return 2. Tính chẵn lẻ của số đá ban đầu xác định bạn nhận 0 hay trọng lượng gốc.

Trọng lượng biên (stones[i] = 1000): hiệu tối đa là 999. Không risk overflow trong Python (integer tùy ý). Trong C#, giá trị là int — hiệu tối đa 999, nằm trong phạm vi int.

So sánh các approach

Ở n=30, cả hai đều pass thoải mái. Nếu bài toán có 1 <= stones.length <= 10^5, approach sort sẽ TLE — mỗi vòng là O(n log n) và bạn có thể có O(n) vòng. Phiên bản heap xử lý được điều đó dễ dàng.

Tôi sẽ ship phiên bản heap trong code production vì nó diễn đạt ý định trực tiếp: "tôi cần truy cập lặp lại vào phần tử lớn nhất." Cách sort-mỗi-vòng là workaround tình cờ hoạt động được.

Mental model: "dynamic max access"

Bài này là ví dụ kinh điển của pattern tôi gọi là dynamic max access: bạn có một tập hợp cần truy cập lặp lại vào maximum (hay minimum), và tập hợp thay đổi giữa các truy vấn. Ngay khi thấy hình dạng đó, heap là câu trả lời. Mảng đã sắp xếp cũng làm được nhưng tốn kém hơn; balanced BST cũng hoạt động nhưng nặng hơn cần thiết.

Trick phủ định trong Python (-stone để mô phỏng max-heap với heapq) đáng nội tâm hóa. Module heap của Python xuất hiện trước khi ngôn ngữ có max-heap trong standard library, và trick này đã là idiom đủ lâu để bạn thấy nó khắp nơi. PriorityQueue của C# với explicit priority value sạch hơn — bạn truyền -stone làm priority mà không cần chạm vào element.

Vị trí trong series

Đây là bài thứ hai trong series heap, ngay sau bài đầu tiên giới thiệu cấu trúc heap. Điều bài này thêm là bước "insert-back": bạn không chỉ rút, mà còn sửa đổi giá trị đã rút và chèn lại. Đó là bước tiến so với bài rút thuần túy.

Các bài tiếp theo tự nhiên là:

• LeetCode 215 — Kth Largest Element in an Array: rút k lần từ max-heap, không reinsert. Vòng lặp đơn giản hơn, cơ chế rút giống nhau.
• LeetCode 703 — Kth Largest Element in a Stream: duy trì min-heap kích thước k để trả lời "phần tử lớn thứ k hiện tại là gì" mỗi lần chèn. Constraint kích thước thay đổi cách bạn nghĩ về cái gì cần giữ.
• LeetCode 621 — Task Scheduler: heap để chọn greedily task thường xuyên nhất còn lại. Bài liên quan đến cooldown, nên bạn cũng quản lý time slot — phức tạp hơn về mặt cấu trúc.
• LeetCode 1642 — Furthest Building You Can Reach: heap để chọn những lần nhảy nào "gán" thang. Kết hợp greedy và heap cổ điển.

Mỗi bài đó thêm một nếp gấp mới. Kth Largest thêm size constraint. Task Scheduler thêm thời gian. Furthest Building thêm choice constraint. Last Stone Weight là phiên bản sạch: chỉ rút, tính, chèn lại, lặp.