Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Xin chào mọi người! Mình là Loser1 từ Learning AI with Loser. Hôm nay chúng ta sẽ đối mặt với con boss cuối – bài Hard thứ hai liên tiếp trong series Daily Challenge! Không sao, cùng mình phân tích từ từ nhé! 🎮
Chào anh em, các ae có thể xem Đề bài và Solution của mình trên LeetCode nhé:
Given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.
Example 1:
Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] Output: 4 Explanation: After the rain, water is trapped between the blocks. We have two small ponds 1 and 3 units trapped. The total volume of water trapped is 4.
Example 2:
Input: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]] Output: 10
Constraints:
m == heightMap.length
n == heightMap[i].length
1 <= m, n <= 200
0 <= heightMap[i][j] <= 2 * 104
Leetcode đưa ra cho chúng ta một ma trận heightMap kích thước m x n, mỗi ô đại diện cho độ cao của một điểm trên bản đồ 2D. Nhiệm vụ của chúng ta là tính toán lượng nước có thể đọng lại sau khi trời mưa. 🌧️
Khi mới nhìn vào bài này, chắc hẳn nhiều bạn cũng như mình, sẽ nhớ ngay đến người anh em "Trapping Rain Water" phiên bản 1D. Ở bài đó, ý tưởng rất đơn giản: với mỗi điểm, ta chỉ cần xác định được "bức tường" cao nhất bên trái và bên phải, lấy min của chúng trừ đi độ cao hiện tại là ra được lượng nước đọng lại tại điểm đó.
Nhưng ở bài này… mọi chuyện phức tạp hơn rồi! 😱
Hãy cùng phân tích chi tiết hơn:
1D: [3,2,1,2,3] → Chỉ xét trái phải
2D: [[3,3,3,3], → Phải xét cả 4 hướng!
[3,1,1,3],
[3,3,3,3]]
Ví dụ với ma trận:
3 3 3 3 3
3 2 1 2 3 → Nước sẽ đọng lại ở các điểm thấp
3 3 3 3 3 nhưng phải được bao quanh bởi các điểm cao hơn
Bắt đầu từ biên → Nước sẽ chảy vào trong Luôn xử lý điểm thấp nhất trước → Min-heap Khi gặp điểm thấp hơn → Có thể đọng nước!
Ban đầu: Sau khi mưa:
1 4 3 1 4 3
3 1 3 → 3 3 3 (số 1 ở giữa đã bị ngập)
2 3 1 2 3 1
Phù! Bài này khá là tricky phải không? Nhưng một khi đã hiểu được ý tưởng cốt lõi, việc implement sẽ trở nên dễ dàng hơn nhiều! 😊
Bonus tip: Khi gặp các bài 2D phức tạp, hãy luôn cố gắng hình dung cách vấn đề hoạt động trong thực tế. Điều này sẽ giúp ta tìm ra hướng giải quyết tự nhiên và hiệu quả hơn!
Okay, giờ chúng ta đã hiểu rõ intuition, hãy cùng đi vào phần implement chi tiết nhé! 🚀
Cùng phân tích từng bước một:
class Solution {
public:
// Hàm kiểm tra xem một ô (i, j) có nằm trong ma trận không
bool is_valid(int i, int j, int m, int n) {
return (i >= 0) && (i < m) && (j >= 0) && (j < n);
}
int trapRainWater(vector<vector<int>>& heightMap) {
// Trả về 0 nếu ma trận đầu vào rỗng
if (heightMap.empty() || heightMap[0].empty()) return 0;
int m = heightMap.size(), n = heightMap[0].size();
// Ma trận đánh dấu các ô đã được thăm
vector<vector<bool>> visited(m, vector<bool>(n, false));
// Sử dụng min-heap để quản lý độ cao nhỏ nhất tại mỗi bước
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> minHeap;
// Thêm các ô ở biên (cạnh trái và cạnh phải) vào heap
for (int i = 0; i < m; i++) {
minHeap.push({heightMap[i][n-1], {i, n-1}});
minHeap.push({heightMap[i][0], {i, 0}});
visited[i][n-1] = visited[i][0] = true; // Đánh dấu các ô này đã được thăm
}
// Thêm các ô ở biên (cạnh trên và cạnh dưới) vào heap
for (int i = 0; i < n; i++) {
minHeap.push({heightMap[m-1][i], {m-1, i}});
minHeap.push({heightMap[0][i], {0, i}});
visited[m-1][i] = visited[0][i] = true; // Đánh dấu các ô này đã được thăm
}
// Các hướng di chuyển (trái, phải, trên, dưới)
vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int trap_water_ans = 0; // Tổng lượng nước bẫy được
// Bắt đầu xử lý các ô trong heap
while (!minHeap.empty()) {
auto [height, cell] = minHeap.top();
minHeap.pop();
int x = cell.first, y = cell.second;
// Duyệt qua các ô lân cận
for (auto [dx, dy] : directions) {
int new_x = x + dx;
int new_y = y + dy;
// Kiểm tra tính hợp lệ và xem ô này đã được thăm chưa
if (is_valid(new_x, new_y, m, n) && !visited[new_x][new_y]) {
// Nếu độ cao hiện tại lớn hơn độ cao ô lân cận, tính nước bẫy được
trap_water_ans += max(0, height - heightMap[new_x][new_y]);
visited[new_x][new_y] = true; // Đánh dấu ô này đã được thăm
// Đưa ô lân cận vào heap với độ cao lớn hơn giữa ô hiện tại và ô lân cận
minHeap.push({max(height, heightMap[new_x][new_y]), {new_x, new_y}});
}
}
}
return trap_water_ans; // Trả về tổng lượng nước bẫy được
}
};
Chúc mọi người code vui! Hẹn gặp lại trong các bài Leetcode tiếp theo! 🚀
P/S: Follow mình tại Learning AI with Loser để cập nhật các bài giải Leetcode hàng ngày nhé! 💻✨
CODE EDITOR
#leetcode #leetcodedaily #algorithms #programming #learningwithlosers