526互联

11、盛水最多的容器

发布时间 2024-01-05 15:48:29作者: 不是孩子了


法一：暴力解法（超时）

int maxArea(vector<int>& height) {
    int max = 0;

    for(int i = 0; i<height.size(); i++){
        for(int j = i+1; j<height.size(); j++){
           int minHeight = min(height[i], height[j]);
           int capacity = (j-i) * minHeight;
           if (capacity > max)
           {
            max = capacity;
           }
        }
    }

    return max;
}

法二：双指针

  1. 设置双指针index1和index2分别指向数组开始和结尾
  2. minHeight为双指针所指元素的较小值
  3. 容积capacity=(index2-index1)*minHeight
  4. 若index1所指元素较短，则index1++后，即移动短板，容积可能增大，可能减小或不变。
  5. 若index2所指元素较长，则index2--后，即移动长板，容积可能不变，可能减小。
  6. 因此只需移动短板，就可能获得较大容积。
int maxArea(vector<int> &height)
{
    int index1 = 0, index2 = height.size() - 1;
    int minHeight = 0;
    int capacity = 0;

    while (index1 != index2)
    {
        if (height[index1] > height[index2])
        {
            minHeight = height[index2];
            if ((index2 - index1) * minHeight > capacity)
            {
                capacity = (index2 - index1) * minHeight;
            }
            index2--;
        }
        else
        {
            minHeight = height[index1];
            if ((index2 - index1) * minHeight > capacity)
            {
                capacity = (index2 - index1) * minHeight;
            }
            index1++;
        }
    }

    return capacity;
}