_Gia_Cat_Luong_
Senior Member
21/06/2022
#1642. (Medium) https://leetcode.com/problems/furthest-building-you-can-reach/Phân tích bài toán:
- 1 <= n <= 10^5: Có thể chạy từ O(nlogn) trở xuống
- Đầu tiên, vì ta bắt buộc phải đi qua từng tòa nhà một theo thứ tự, nên chỉ cần quan tâm độ cao chênh lệch giữa 2 tòa nhà liên tiếp nhau
- Hay nói cách khác, giá trị đáng quan tâm là h = heights - heights[i - 1] với i = 1 → n
- Nếu h ≤ 0 thì ta được free 1 tòa nhà, ngược lại, ta sẽ lựa chọn dùng gạch hoặc thang để vượt qua tòa nhà
- Dễ thấy thang hiệu quả hơn dùng gạch rất nhiều vì có thể vượt qua bất kì độ cao nào, trong khi gạch thì càng cao chi phí càng lớn
- Suy ra, bài toán chính là tối ưu khi nào nên dùng thang khi nào nên dùng gạch. Hay cách khác, chính là dùng thang sao cho tối ưu nhất có thể
Vậy dùng thang sao cho tối ưu ?
- Giả sử chỉ có 1 thang:
- Rõ ràng ta chỉ nên dùng nó ở vị trí có h cao nhất, các chỗ khác thì dùng gạch cho tiết kiệm
- Nhưng nếu vị trí đó nằm ở cuối mảng, mà ta không có đủ gạch để đi đến đó ? Vậy thì phải chọn vị trí có h cao nhất nhưng trước khi hết gạch
- Mở rộng ra, nếu có 2 thang thì sao ? Ta sẽ dùng 2 thang ở vị trí có h lớn nhất và nhì trước khi hết gạch
- Tương tự với n thang, ta sẽ dùng nó cho n vị trí lớn nhất có thể trước khi hết gạch
Vậy ta đã có phương án cơ bản, vấn đề trở thành làm thế nào để tìm được n vị trí lớn nhất này trước khi hết gạch ?
- Trước tiên cứ keep in mind, khi nào gặp bài toán top k phần tử lớn nhất / bé nhất thì khả năng cao ta sẽ dùng heap (Priority Queue). Vì đây là CDTL tối ưu cho bài toán này
- Nhưng dùng heap như thế nào ? Ta phân tích tiếp. Nếu giả sử chỉ có 1 thang, ta sẽ:
- Dùng gạch hết mức có thể
- Lưu lại trước đó ta đã đi qua tòa nhà có h cao nhất là hmax
- Rõ ràng để tối ưu ta sẽ dùng thang tại vị trí hmax, nếu thế ta tiết kiệm đc hmax viên gạch
- Vì hết thang rồi, nên ta tiếp tục xài số gạch còn lại (+ hmax tiết kiệm được) để đi tiếp
- Đi hết gạch luôn thì thôi, tòa nhà cuối cùng đang đứng chính là đáp án
- Nếu có 2 thang?
- Làm tương tự như khi có 1 thang
- Nhưng khi đến hết gạch lần đầu tiên, vì ta còn thừa 1 thang, nên ta lại lặp lại như trước:
- Tìm tòa nhà có h lớn nhất đã qua (nhưng không bao gồm cái đã chọn lần trước)
- Dùng thang chỗ đó, tiết kiệm đc số gạch tương ứng
- Xài hết gạch rồi nghỉ
- Đến đây có lẽ đáp án đã rõ ràng, với n thang
- Xài hết gạch có thể, lưu lại các vị trí đã qua
- Tìm tòa nhà có h lớn nhất trong các tòa đã qua (mà chưa chọn trước đó)
- Nếu còn thang, dùng 1 thang tại vị trí đó, tiết kiệm đc số gạch tương ứng, lặp lại bước trên
- Nếu hết thang, nghỉ khỏe
- Câu hỏi cuối cùng là làm sao để tìm được tòa nhà có h lớn nhất trong các tòa đã qua ? Đáp án nằm ở ngay ý đầu tiên của phần này ?
Solution
Mã giả:
Nhận xét:
Code:
pq = new <Heap Max>
for <i từ 1 đến heights.length> {
h = heights[i] - heights[i - 1]
if (h <= 0) continue // bỏ qua
// Dùng gạch
bricks -= h
pq.push(h)
if (bricks >= 0) continue; // vẫn còn đủ gạch thì đi tiếp
// hết gạch thì dùng thang
if (ladders <= 0) return i - 1 // Hết thang luôn thì nghỉ khỏe
ladders -= 1 // dùng 1 thang
bricks += pq.pop() // tiết kiệm số gạch lớn nhất có thể
}
return heights.length - 1Nhận xét:
- Solution này có độ phức tạp O(nlogn) cho các thao tác trên heap
- Đây là một giải pháp greedy vì với mỗi bước ta chỉ quan tâm đến việc vượt qua tòa nhà trước mắt chứ không tính toán cho các trường hợp lâu dài
Last edited:
. Nay lại học thêm đc chiêu này.
. Lâu lâu có bài dễ xả stress chứ.
