Bài 42 Leetcode: Trapping Rain Water

Đề bài:

Cho n số nguyên không âm đại diện cho một bản đồ độ cao nơi chiều rộng của mỗi thanh là 1, tính toán lượng nước mà nó có thể giữ sau một trận mưa.

Ví dụ 1:

Trapping Rain Water
Trapping Rain Water
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Giải thích: Bản đồ độ cao trên (phần đen) được biểu diễn bởi mảng [0,1,0,2,1,0,1,3,2,1,2,1]. Trong trường hợp này, có 6 đơn vị nước mưa (phần màu xanh) được giữ lại.

Ví dụ 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Ràng buộc:

  • n == độ dài của height
  • 1 <= n <= 2 * 10^4
  • 0 <= height[i] <= 10^5

Cách1: O(n) space

Giải thích thuật toán bằng C ++

class Solution {
 public:
  int trap(vector<int>& height) {
    const int n = height.size();
    int ans = 0;
    vector<int> l(n);  // l[i] := max(height[0..i])
    vector<int> r(n);  // r[i] := max(height[i..n))

    for (int i = 0; i < n; ++i)
      l[i] = i == 0 ? height[i] : max(height[i], l[i - 1]);

    for (int i = n - 1; i >= 0; --i)
      r[i] = i == n - 1 ? height[i] : max(height[i], r[i + 1]);

    for (int i = 0; i < n; ++i)
      ans += min(l[i], r[i]) - height[i];

    return ans;
  }
};

Đoạn mã trên là một đoạn mã C++ để tính toán lượng nước mà một bản đồ độ cao có thể giữ được sau một trận mưa. Dưới đây là giải thích về thuật toán trong đoạn mã:

1. Hàm `trap` nhận một vector `height` là mảng các số nguyên đại diện cho độ cao của các thanh và trả về tổng lượng nước mà bản đồ độ cao có thể giữ được.

2. Đầu tiên, ta khai báo một hằng số `n` để lưu độ dài của mảng `height`.

3. Tiếp theo, ta khởi tạo hai mảng `l` và `r` có độ dài `n`, trong đó `l[i]` đại diện cho giá trị cao nhất từ độ cao `height[0]` đến `height[i]`, và `r[i]` đại diện cho giá trị cao nhất từ độ cao `height[i]` đến `height[n-1]`.

4. Sử dụng hai vòng lặp, ta đi qua mảng `height` từ trái sang phải và từ phải sang trái để tính toán các giá trị của `l` và `r`. Trong quá trình này, ta sử dụng hàm `max` để lấy giá trị cao nhất giữa `height[i]` và giá trị trước đó trong mảng `l` (đối với vòng lặp từ trái sang phải) hoặc giá trị sau đó trong mảng `r` (đối với vòng lặp từ phải sang trái). Điều này giúp ta xác định giá trị cao nhất trong các đoạn độ cao từ các vị trí trước và sau vị trí hiện tại.

5. Sau khi tính toán xong giá trị của `l` và `r`, ta sử dụng một vòng lặp để tính tổng lượng nước được giữ lại. Trong vòng lặp này, ta tính toán độ cao tối thiểu giữa `l[i]` và `r[i]` (đại diện cho độ cao tối thiểu của hai cạnh bên của một vùng nước) và trừ đi độ cao thực tế tại vị trí `i` trong mảng `height`. Kết quả được cộng vào biến `ans`.

6. Cuối cùng, ta trả về giá trị `ans` là tổng lượng nước mà bản đồ độ cao có thể giữ được.

Thuật toán trên sử dụng hai mảng `l` và `r` để lưu trữ các giá trị cao nhất từ các vị trí trước và sau của mỗi vị trí trong mảng `height`. Sau đó, ta tính toán tổng lượng nước được giữ lại bằng cách tính toán độ cao tối thiểu giữa hai cạnh bên và trừ đi độ cao thực tế tại mỗi vị trí.

Giải thích thuật toán bằng Java

class Solution {
  public int trap(int[] height) {
    final int n = height.length;
    int ans = 0;
    int[] l = new int[n]; // l[i] := max(height[0..i])
    int[] r = new int[n]; // r[i] := max(height[i..n))

    for (int i = 0; i < n; ++i)
      l[i] = i == 0 ? height[i] : Math.max(height[i], l[i - 1]);

    for (int i = n - 1; i >= 0; --i)
      r[i] = i == n - 1 ? height[i] : Math.max(height[i], r[i + 1]);

    for (int i = 0; i < n; ++i)
      ans += Math.min(l[i], r[i]) - height[i];

    return ans;
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def trap(self, height: List[int]) -> int:
    n = len(height)
    l = [0] * n  # l[i] := max(height[0..i])
    r = [0] * n  # r[i] := max(height[i..n))

    for i, h in enumerate(height):
      l[i] = h if i == 0 else max(h, l[i - 1])

    for i, h in reversed(list(enumerate(height))):
      r[i] = h if i == n - 1 else max(h, r[i + 1])

    return sum(min(l[i], r[i]) - h
               for i, h in enumerate(height))

Cách 2: O(1) space

Giải thích thuật toán bằng C ++

class Solution {
 public:
  int trap(vector<int>& height) {
    if (height.empty())
      return 0;

    int ans = 0;
    int l = 0;
    int r = height.size() - 1;
    int maxL = height[l];
    int maxR = height[r];

    while (l < r)
      if (maxL < maxR) {
        ans += maxL - height[l];
        maxL = max(maxL, height[++l]);
      } else {
        ans += maxR - height[r];
        maxR = max(maxR, height[--r]);
      }

    return ans;
  }
};

Đoạn mã trên triển khai thuật toán để tính toán lượng nước có thể giữa các cột trong một mảng chiều cao.

Thuật toán này hoạt động như sau:

1. Kiểm tra nếu mảng `height` rỗng, tức là không có cột nào, ta trả về 0.

2. Khởi tạo biến `ans` để lưu tổng lượng nước có thể giữa các cột, và các biến `l` và `r` để định vị hai chỉ số của cột bên trái và bên phải.

3. Khởi tạo biến `maxL` và `maxR` để lưu chiều cao lớn nhất đã được ghi nhận từ bên trái và bên phải.

4. Thực hiện vòng lặp `while` cho đến khi chỉ số `l` vượt qua chỉ số `r`.

5. Trong mỗi vòng lặp, kiểm tra nếu `maxL` nhỏ hơn `maxR`. Điều này có nghĩa là chiều cao của cột tại vị trí `l` thấp hơn chiều cao của cột tại vị trí `r`.

– Tăng `ans` thêm giá trị `(maxL – height[l])`, đại diện cho lượng nước có thể giữa cột tại vị trí `l` và `maxL`.

– Cập nhật `maxL` bằng cách so sánh `maxL` và `height[l]`.

– Tăng `l` lên 1 đơn vị.

6. Nếu `maxL` không nhỏ hơn `maxR`, ta sẽ thực hiện các bước tương tự cho cột bên phải.

– Tăng `ans` thêm giá trị `(maxR – height[r])`, đại diện cho lượng nước có thể giữa cột tại vị trí `r` và `maxR`.

– Cập nhật `maxR` bằng cách so sánh `maxR` và `height[r]`.

– Giảm `r` xuống 1 đơn vị.

7. Kết thúc vòng lặp, ta trả về giá trị `ans` là tổng lượng nước có thể giữa các cột.

Thuật toán này dựa trên ý tưởng hai con trỏ. Ta duyệt từ hai phía của mảng, đồng thời cập nhật chiều cao lớn nhất đã ghi nhận từ bên trái và bên phải. Khi ta tăng con trỏ bên trái hoặc giảm con trỏ bên phải, ta có thể tính toán lượng nước có thể giữa các cột theo chiều cao lớn nhất đã ghi nhận.

Giải thích thuật toán bằng Java

class Solution {
  public int trap(int[] height) {
    if (height.length == 0)
      return 0;

    int ans = 0;
    int l = 0;
    int r = height.length - 1;
    int maxL = height[l];
    int maxR = height[r];

    while (l < r)
      if (maxL < maxR) {
        ans += maxL - height[l];
        maxL = Math.max(maxL, height[++l]);
      } else {
        ans += maxR - height[r];
        maxR = Math.max(maxR, height[--r]);
      }

    return ans;
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def trap(self, height: List[int]) -> int:
    if not height:
      return 0

    ans = 0
    l = 0
    r = len(height) - 1
    maxL = height[l]
    maxR = height[r]

    while l < r:
      if maxL < maxR:
        ans += maxL - height[l]
        l += 1
        maxL = max(maxL, height[l])
      else:
        ans += maxR - height[r]
        r -= 1
        maxR = max(maxR, height[r])

    return ans

 

Leave a Reply

Your email address will not be published. Required fields are marked *

PHP Code Snippets Powered By : XYZScripts.com
.
.
.
.