Menu Close

Container With Most Water Problem

Follow me on :
– Youtube: https://bit.ly/2UIVIAD
– Facebook: https://bit.ly/2XbMYow

Problem

Given n non-negative integers a1a2, …, a, where each represents a point at coordinate (iai). n vertical lines are drawn such that the two endpoints of line i is at (iai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

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< int > &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 thời gian: O(n)
Độ phức tạp không gian: O(1)

int maxArea(vector< int > &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;
}

Leave a Reply

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