找到最大可能的区域

Question

给定n个非负整数a1， a2，...， an，其中每个表示坐标（i， ai）处的点。绘制n条垂直线，使得线i的两个endpoint位于（i， ai）和（i，0）。找到两条线，它们与x轴一起构成一个容器，使得容器中包含最多的水。

注意：容器不能倾斜。

一种解决方案可能是我们取每一行并找到每一行的区域。这需要O（n^2）。没有时间效率。

另一种解决方案是使用DP找到每个索引的最大面积，然后在索引n处，我们将得到最大面积。我想是O（n）。

有没有更好的解决方案？

Answer 1

这是一个Java实现：

基本思想是使用前后两个指针，并计算沿途的面积。

public int maxArea(int[] height) {
    int i = 0, j = height.length-1;
    int max = Integer.MIN_VALUE;

    while(i < j){
        int area = (j-i) * Math.min(height[i], height[j]);
        max = Math.max(max, area);
        if(height[i] < height[j]){
            i++;
        }else{
            j--;
        }
    }

    return max;
}

Answer 2

这里的许多人把这个问题误认为是最大矩形问题，事实并非如此。

解决方案

1. 删除所有元素aj，以便ai

1. 查找ai和aj之间的区域并跟踪最大值

复杂度是线性的（O（n））

Answer 3

int maxArea(vector<int> &height) {
    int ret = 0;
    int left = 0, right = height.size() - 1;
    while (left < right) {
        ret = max(ret, (right - left) * min(height[left], height[right]));
        if (height[left] <= height[right])
            left++;
        else
            right--;
    }
    return ret;
}