Chứa đựng nước nhiều nhất trong C++

Chúng ta được cho một mảng chiều cao các bức tường của container. Mục tiêu là tìm container có thể chứa thể tích nước lớn nhất. Vì chiều cao tường là các phần tử mảng, khoảng cách giữa chúng được coi là chiều rộng giữa hai tường. Ví dụ tường chiều cao Arr[i] và Arr[j] có chiều rộng j-i (0 <= i < j <= N), trong đó N là số tường hoặc độ dài mảng.

Vì vậy chiều cao nước sẽ đến tường thấp hơn, nếu Arr[i] < Arr[j] thì chiều cao nước là Arr[i]. Chiều rộng là j-i nên diện tích nước = Arr[i] * (j - i).

Chúng ta phải tìm diện tích lớn nhất như vậy.

Ví dụ

Đầu vào

Arr[] = { 5, 1, 2, 3, 5 }

Đầu ra

Diện tích nước tối đa: 20

Giải thích

Chứa đựng nước nhiều nhất trong C++

Như hình vẽ, với chiều cao tường 5, 1, 2, 3 và chiều rộng tối đa giữa các tường là

Arr[0] và Arr[4] width=4, area = Arr[0] <= Arr[4] → 5*4=20
Arr[1] và Arr[4] width=3, area = Arr[1] <= Arr[4] → 1*4=4
Arr[2] và Arr[0] hoặc Arr[4] width=4, area = Arr[0] <= Arr[0] → 2*2=4
Arr[3] và Arr[0] width=3, area = Arr[0] <= Arr[0] → 3*3=9
Arr[4] và Arr[0] width=4, area = Arr[0] <= Arr[4] → 5*4=20

Container diện tích tối đa sẽ chứa nhiều nước nhất, diện tích=20, tường Arr[0] và Arr[4].

Đầu vào

Arr[] = { 1, 5, 4, 3, 2, 4 }

Đầu ra

Diện tích nước tối đa: 16

Giải thích

Arr[0] và Arr[5] width=5, area = Arr[0] <= Arr[5] → 1*5=5
Arr[1] và Arr[5] width=4, area = Arr[1] <= Arr[5] → 4*4=16
Arr[2] và Arr[5] width=3, area = Arr[2] <= Arr[5] → 3*4=12
Arr[3] và Arr[1] width=2, area = Arr[3] <= Arr[1] → 3*2=6
Arr[4] và Arr[1] width=3, area = Arr[1] <= Arr[4] → 2*3=6
Arr[5] và Arr[1] width=4, area = Arr[1] <= Arr[4] → 4*4=16

Container diện tích tối đa sẽ chứa nhiều nước nhất, diện tích=16, tường Arr[0] và Arr[4].

Phương pháp sử dụng trong chương trình dưới đây

Mảng số nguyên walls[] chứa chiều cao các tường.
Hàm mostwater(int A[], int len) nhận mảng chiều cao và số phần tử, trả về diện tích container chứa nhiều nước nhất vì chỉ có chiều cao và chiều rộng.
Lấy hai chỉ số r = len-1 và l = 0 để duyệt mảng từ cả hai đầu.
Số nguyên area và maxarea lưu diện tích container hiện tại và diện tích container tối đa tìm thấy cho đến nay. Khởi tạo 0.
int minwall, lwall, rwall lưu chiều cao tường trái (A[l]), tường phải (A[r]), và chiều cao nhỏ nhất của lwall và rwall.
While (l < r) duyệt mảng và với mỗi A[l] và A[r], chiều cao nước sẽ là nhỏ hơn của hai. Cái nào nhỏ hơn lưu vào minwall.
Chiều rộng giữa hai tường là hiệu chỉ số (r - l).
Tính diện tích nước/container = minwall * (r - l) và cập nhật area.
Làm vậy cho tất cả tường, nếu diện tích hiện tại là tối đa cho đến nay thì cập nhật maxarea.
Cuối cùng maxarea sẽ có diện tích container chứa nhiều nước nhất.
Trả về maxarea làm kết quả.

Ví dụ mã nguồn

#include <iostream> 
using namespace std; 

int mostwater(int A[], int len) { 
    int r = len - 1; // chỉ số tường phải container
    int l = 0; // chỉ số tường trái container
    int area = 0, maxarea = 0; 
    int minwall, lwall, rwall; 
    while (l < r) { 
        // Tính diện tích tối đa
        lwall = A[l]; // chiều cao tường trái container
        rwall = A[r]; // chiều cao tường phải container
        minwall = lwall <= rwall ? lwall : rwall; // min của hai tường là chiều cao nước
        area = minwall * (r - l); // diện tích là min wall * width (r-l)
        maxarea = area >= maxarea ? area : maxarea; 
        if (l < r) 
            l += 1; 
        else 
            r -= 1; 
    } 
    return maxarea; 
} 

int main() { 
    int walls[] = {1, 5, 4, 3, 2, 4}; 
    int num = sizeof(walls) / sizeof(walls[0]); 
    cout << endl << "Container chứa nhiều nước nhất có diện tích: " << mostwater(walls, num); 
}

Kết quả

Container chứa nhiều nước nhất có diện tích: 16