Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Leetcode Logo

LeetCode Daily Challenge -Day10: 407. Trapping Rain Water II

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àiSolution của mình trên LeetCode nhé:

407. Trapping Rain Water II

Hard
Solved 2069 Accepted

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 1

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
Example 2

Constraints:

  • m == heightMap.length
  • n == heightMap[i].length
  • 1 <= m, n <= 200
  • 0 <= heightMap[i][j] <= 2 * 104

Problem Statement

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. 🌧️

First Thoughts & Intuition

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:

  1. Từ 1D lên 2D:
   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]]
  • Trong 1D: nước chỉ có thể chảy sang trái hoặc phải
  • Trong 2D: nước có thể chảy theo 4 hướng!
  1. Quan sát thực tế:
   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
  • Nước chỉ đọng lại ở những vùng "trũng"
  • Độ cao của nước phụ thuộc vào bức tường thấp nhất xung quanh
  • Nước sẽ tràn ra ngoài nếu không có bức tường đủ cao chặn lại
  1. Moment "Eureka"! 💡
  • Thay vì cố gắng tính toán từng ô một cách riêng lẻ
  • Ta có thể mô phỏng cách nước chảy trong thực tế:
    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!
  1. Ví dụ cụ thể:
   Ban đầu:    Sau khi mưa:
   1 4 3       1 4 3
   3 1 33 3 3   (số 1 ở giữa đã bị ngập)
   2 3 1       2 3 1
  • Điểm có độ cao 1 ở giữa bị bao quanh bởi các điểm cao hơn
  • Nước sẽ dâng lên đến độ cao của điểm thấp nhất xung quanh
  • → Lượng nước đọng = min(các điểm xung quanh) - độ cao hiện tại
  1. Chiến lược tối ưu:
  • Sử dụng min-heap để luôn xử lý các điểm theo thứ tự độ cao tăng dần
  • Bắt đầu từ biên (vì nước không thể đọng ở biên)
  • Lan dần vào trong, cập nhật độ cao của các điểm sau khi nước đọng
  • Giống như việc đổ nước vào một cái khay và xem nó chảy đi đâu!

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é! 🚀

Approach

Cùng phân tích từng bước một:

  1. Xác định biên:
  • Đầu tiên, ta cần nhận ra rằng các ô ngoài cùng sẽ không thể giữ nước
  • Chúng sẽ là "bức tường" đầu tiên của chúng ta
  1. Min-heap Strategy:
  • Sử dụng min-heap để luôn xử lý các điểm thấp nhất trước
  • Điều này giống như việc nước sẽ tràn qua điểm thấp nhất trước
  1. Mở rộng dần từ ngoài vào trong:
  • Từ biên, ta sẽ dần dần "lấp đầy" các ô bên trong
  • Nếu gặp ô thấp hơn → có thể đọng nước
  • Nếu gặp ô cao hơn → tạo thành bức tường mới

Code Implementation

C++
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
    }
};

Complexity Analysis

  • Time: O(m * n * log(m * n)) - mỗi ô được xử lý một lần và các thao tác với heap
  • Space: O(m * n) - cho heap và ma trận visited

Key Insights

  1. Tư duy như nước: Nước luôn chảy từ cao xuống thấp, và chỉ đọng lại ở những vùng trũng
  2. Min-heap Magic: Việc sử dụng min-heap giúp ta luôn xử lý các điểm theo thứ tự tối ưu
  3. Boundary First: Bắt đầu từ biên giúp ta không bỏ sót trường hợp nào

Tips & Tricks

  1. Luôn vẽ hình để hình dung vấn đề rõ ràng hơn
  2. Đừng ngại các bài Hard! Phân tích từng bước sẽ thấy chúng không quá khó
  3. Test với các edge cases như ma trận rỗng, ma trận 1x1, etc.

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

quyminhhuy0@gmail.com
quyminhhuy0@gmail.com
Articles: 39

Newsletter Updates

Enter your email address below and subscribe to our newsletter

Subscribe
Notify of
guest

0 Comments
Inline Feedbacks
View all comments
AI Assistant
Hi! How can I help you today?
Heavy equipment transport will il. Máy lọc dầu chân không inox.