# Container With Most Water Problem

blackntt

# Problem

Cho một dãy số nguyên không âm a1, a2,..., an. Mỗi số nguyên với ở vị trí i sẽ biểu diễn một điểm ở biểu đồ có toạ độ (i, ai). Tương ứng với mảng số nguyên n phần tử sẽ vẽ tương ứng n cột giữa 2 điểm (i,0) và (i,ai). Yêu cầu tìm 2 cột mà hình chữ nhật tạo bởi 2 cột sau khi hợp với trục ox sẽ có khả năng chứa nhiều nước nhất và xuất ra lượng nước có thể chứa tối đa đó.

Ví dụ

Input: [1,8,6,2,5,4,8,3,7] Output: 49

# Solution

# Giải pháp Brute force:

Độ phức tạp thời gian: 0(n^2) Độ phức tạp không gian: O(1)

int maxArea(vector &height)
{
    int maxWater = INT_MIN;
    for (int i = 0; i < height.size(); i++)
    {
        for (int j = i+1; j < height.size(); j++)
        {
            int water = min(height[i],height[j])*(j-i);
            maxWater = max(maxWater,water);
        }

    }
    return maxWater;
}

# Giải pháp two pointer:

Độ phức tạp

Độ phức tạp thời gian: O(n)
Độ phức tạp không gian: O(1)

int maxArea(vector &height)
{
    int maxWater = INT_MIN;
    int l = 0, r = height.size() - 1;
    while (l < r)
    {
        int water = min(height[l], height[r]) * (r - l);
        maxWater = max(maxWater, water);
        if(height[l] < height[r]){
            l++;
        }else{
            r--;
        }
    }
    return maxWater;
}

algorithm algorithms c++ container with most water leetcode thuật toán