2

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

注意：您不能倾斜容器。

一种解决方案可能是我们采用每条线并找到每条线的区域。这需要 O(n^2)。时间效率不高。

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

能有更多更好的解决方案吗？

4

7 回答 7

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;
}
于 2013-01-27T20:54:40.460 回答
2

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

解决方案

  1. 删除所有元素 aj 使得 ai >= aj =< ak 并且 i > j < k。这可以在线性时间内完成。
    1. 找到最大值 am
    2. 让 as = a1
    3. 对于 j = 2 到 m-1，如果 as >= aj，则删除 aj，否则 as = aj
    4. 让 as = an
    5. 对于 j = n-1 到 m+1，如果 as >= aj，则删除 aj，否则 as = aj
  2. 请注意，结果值看起来像一个金字塔，即最大值左侧的所有元素都严格递增，右侧的所有元素严格递减。
  3. i=1，j=n。m 是最大值的位置。
  4. 而 i<=m 和 j>=m
    1. 查找 ai 和 aj 之间的区域并跟踪最大值
    2. 如果 ai < aj，i+=1，否则 j-=1

复杂度是线性的 (O(n))

于 2012-05-20T16:09:35.840 回答
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;
}
于 2013-11-03T20:39:41.520 回答
1

这是一个干净的 Python3 解决方案。此解决方案的运行时间为 O(n)。重要的是要记住，两条线之间形成的区域由较短线的高度和线之间的距离决定。

def maxArea(height):
    """
    :type height: List[int]
    :rtype: int
    """
    left = 0
    right = len(height) - 1
    max_area = 0
    while (left < right):
        temp_area = ((right - left) * min(height[left], height[right]))
        if (temp_area > max_area):
            max_area = temp_area
        elif (height[right] > height[left]):
            left = left + 1
        else:
            right = right - 1
    return max_area
于 2018-07-16T08:44:27.507 回答
0

这个问题可以在线性时间内解决。

  1. 构造一个可能的左墙列表（位置+高度对），按从高到低的顺序排列。这是通过获取最左边的可能墙并将其添加到列表中来完成的，然后从左到右遍历所有可能的墙，并获取所有大于添加到列表中的最后一堵墙的墙。例如，对于数组

    2 5 4 7 3 6 2 1 3

    你可能的左墙将是（对是（pos，val））：

    (3, 7) (1, 5) (0, 2)

  2. 以相同的方式构建可能的右墙列表，但从右到左。对于上面的数组，可能的右墙是：

    (3, 7) (5, 6) (8, 3)

  3. 开始你的水位尽可能高，这是两个列表前面墙壁的最小高度。使用这些墙壁计算水的总体积（它可能是负数或零，但没关系），然后通过从其中一个列表中弹出一个元素来降低水位，以使水位下降最少。计算每个高度的可能水量并取最大值。

在这些列表上运行此算法将如下所示：

L: (3, 7) (1, 5) (0, 2)  # if we pop this one then our water level drops to 5
R: (3, 7) (5, 6) (8, 3)  # so we pop this one since it will only drop to 6
Height = 7
Volume = (3 - 3) * 7 = 0
Max = 0

L: (3, 7) (1, 5) (0, 2)  # we pop this one now so our water level drops to 5
R: (5, 6) (8, 3)         # instead of 3, like if we popped this one
Height = 6
Volume = (5 - 3) * 6 = 12
Max = 12

L: (1, 5) (0, 2)
R: (5, 6) (8, 3)
Height = 5
Volume = (5 - 1) * 5 = 20
Max = 20


L: (1, 5) (0, 2)
R: (8, 3)
Height = 3
Volume = (8 - 1) * 3 = 21
Max = 21

L: (0, 2)
R: (8, 3)
Height = 2
Volume = (8 - 0) * 2 = 16
Max = 21

步骤 1、2 和 3 都以线性时间运行，因此完整的解决方案也需要线性时间。

于 2012-05-20T21:32:12.457 回答
0

最好的答案是Black_Rider，但是他们没有提供解释。

我在这个博客上找到了一个非常清楚的解释。很快，情况如下：

给定长度为 n 的数组高度：

  1. 从你能做到的最宽的容器开始，即从 0 处的左侧到 n-1 处的右侧。

  2. 如果存在更好的容器，它将更窄，因此它的两侧必须高于当前选择的低侧。

  3. 因此，如果 height[left] < height[right]，则将 left 更改为 (left+1)，否则将 right 更改为 (right-1)。

  4. 计算新的面积，如果它比你目前的更好，更换。

  5. 如果左 < 右，则从 2 开始。

我在 C++ 中的实现：

int maxArea(vector<int>& height) {
    auto current = make_pair(0, height.size() - 1);
    auto bestArea = area(height, current);

    while (current.first < current.second) {
        current = height[current.first] < height[current.second]
            ? make_pair(current.first + 1, current.second)
            : make_pair(current.first, current.second - 1);

        auto nextArea = area(height, current);
        bestArea = max(bestArea, nextArea);
    }

    return bestArea;
}

inline int area(const vector<int>& height, const pair<int, int>& p) {
    return (p.second - p.first) * min(height[p.first], height[p.second]);
}
于 2016-10-17T12:06:30.163 回答
-1

这个问题是The Maximal Rectangle Problem的一个更简单的版本。给定的情况可以看作是一个二进制矩阵。将矩阵的行视为 X 轴，将列视为 Y 轴。对于数组中的每个元素 a[i]，设置

Matrix[i][0] = Matrix[i][1] = ..... = Matrix[i][a[i]] = 1

例如 - For a[] = { 5, 3, 7, 1}，我们的二进制矩阵由下式给出：

1111100
1110000
1111111
1000000
于 2012-05-20T14:40:36.293 回答