Bài 11 Leetcode: Container With Most Water

Đề bài:

Bạn được cho một mảng số nguyên height có độ dài n. Có n đường dọc được vẽ sao cho hai đầu mút của đường thứ i ^th là (i, 0) và (i, height[i]). Tìm hai đường sao cho cùng với trục x tạo thành một bình chứa, sao cho bình chứa đó chứa được lượng nước lớn nhất. Trả về lượng nước tối đa mà một bình chứa có thể chứa được. Lưu ý rằng bạn không thể làm nghiêng bình chứa.

Ví dụ 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Giải thích: Các đường dọc trên được biểu diễn bởi mảng [1,8,6,2,5,4,8,3,7]. Trong trường hợp này, diện tích nước tối đa (phần màu xanh) mà bình chứa có thể chứa được là 49.

Ví dụ 2:

Input: height = [1,1]
Output: 1

Ràng buộc:

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

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

class Solution {
 public:
  int maxArea(vector<int>& height) {
    int ans = 0;
    int l = 0;
    int r = height.size() - 1;

    while (l < r) {
      const int minHeight = min(height[l], height[r]);
      ans = max(ans, minHeight * (r - l));
      if (height[l] < height[r])
        ++l;
      else
        --r;
    }

    return ans;
  }
};

Đây là một đoạn mã trong ngôn ngữ C++ để triển khai hàm maxArea(vector<int>& height) theo thuật toán đã mô tả trước đó. Dưới đây là giải thích chi tiết về thuật toán này:

1. Hàm maxArea(vector<int>& height): Đây là hàm chính để tìm diện tích lớn nhất của bình chứa dựa trên chiều cao các đường dọc. Hàm này nhận đầu vào là một vector height chứa các giá trị chiều cao của các đường dọc.

2. Khởi tạo biến ans = 0 để lưu trữ diện tích lớn nhất tìm được.

3. Khởi tạo biến l = 0 và r = height.size() – 1, đại diện cho chỉ số của hai đầu mút trái và phải của bình chứa.

4. Thực hiện vòng lặp while cho đến khi l >= r:

– Gán minHeight = min(height[l], height[r]), đại diện cho chiều cao nhỏ nhất giữa hai đường dọc l và r. Đây sẽ là chiều cao của bình chứa trong trường hợp này.

– Gán ans = max(ans, minHeight * (r – l)), đại diện cho diện tích hiện tại của bình chứa. Nếu diện tích này lớn hơn diện tích lớn nhất đã tìm thấy, cập nhật ans.

– Nếu height[l] < height[r], tăng l lên 1 để di chuyển đầu mút trái về phía bên phải.

– Ngược lại, giảm r đi 1 để di chuyển đầu mút phải về phía bên trái.

5. Trả về giá trị ans, tức là diện tích lớn nhất của bình chứa.

Thuật toán này sử dụng kỹ thuật hai con trỏ (two pointers) để duyệt qua các đường dọc và tìm ra diện tích lớn nhất của bình chứa. Bằng cách di chuyển con trỏ trái và con trỏ phải dựa trên chiều cao của đường dọc, thuật toán đảm bảo xét tất cả các khả năng và trả về diện tích lớn nhất tìm được.

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

class Solution {
  public int maxArea(int[] height) {
    int ans = 0;
    int l = 0;
    int r = height.length - 1;

    while (l < r) {
      final int minHeight = Math.min(height[l], height[r]);
      ans = Math.max(ans, minHeight * (r - l));
      if (height[l] < height[r])
        ++l;
      else
        --r;
    }

    return ans;
  }
}

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

class Solution:
  def maxArea(self, height: List[int]) -> int:
    ans = 0
    l = 0
    r = len(height) - 1

    while l < r:
      minHeight = min(height[l], height[r])
      ans = max(ans, minHeight * (r - l))
      if height[l] < height[r]:
        l += 1
      else:
        r -= 1

    return ans