查找最大可能區域

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