查找最大可能区域

Question

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

注意：您不得倾斜容器。

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

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

难道还有更好的解决方案吗？

Answer 1

很多人都误以为这个问题最大的矩形问题，情况并非如此。

解

1. 删除所有元素第j使得AI> = AJ = < AK和I>Ĵ<ķ。这可以在线性时间完成。
   1. 找到最大值是
   2. 让作为= A1
   3. 对于j = 2至m-1，如果为> = AJ，删除AJ，否则如=第j
   4. 让尽可能=一个
   5. 对于j = N-1至m + 1，如果为> = AJ，删除AJ，否则如=第j
2. 注意，所得到的值看起来像一个金字塔，即，在左侧的所有元素的最大值是严格递增的，右边是严格递减的。
3. i = 1，j = n。 m是最大的位置。
4. 虽然我< = M且j> = Ai和Aj和保持最大的轨道之间米
   1. 查找区域
   2. 如果AI < AJ，I + = 1，否则J- = 1

复杂性是线性的（O（N））

Answer 2

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

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

对于如 - 对于a[] = { 5, 3, 7, 1}，我们的二元矩阵由下式给出：

这里

1111100 
1110000 
1111111 
1000000 

Answer 3

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

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的线性时间都运行的，所以完整的解决方案也需要线性时间。

Answer 4

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; 
} 

Answer 5

下面是与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 6

The best answer是Black_Rider，但是他们并没有提供解释。

我在this blog上发现了一个非常明确的解释。不久，这是不言而喻如下：在第n-1

1. 开始就可以在0到右侧最宽的容器，即，从左侧：

   长度为n的给定阵列的高度。

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

3. 因此，如果高度[左] <高度[右]，则将左侧更改为（左侧+1），否则右侧更改为（右侧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]); 
}