011 Container With Most Water[M]

02-25

1 題目描述

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.

難度：Medium

2 題目樣例

無

3 題意分析

意思就是n個豎直的桿，任選兩個加上底面所能構成的容器最大容積。

也就是說假設選定 $(x,a_x)$ 和 $(y,a_y)$ ，那麼容積為 $|x-y|*min(a_x,a_y)$ 。

（此處我們可以鑽牛角尖，container難道不是個三維的嗎！（逃

4 思路分析

$O(n^2)$ 的暴力演算法非常容易想到，只要枚舉即可，這裡略去。

那麼如何優化呢？

我們設置兩個指針，其中一個從頭開始遍歷，一個從尾開始遍歷，假設分別為 $(x,a_x)$ 和 $(y,a_y)$ 並且 $xle y$ 並且 $a_x le a_y$ ，那麼我們可以確定 $(x,a_x)$ 和 $(y-1,a_{y-1}),(y-2,a_{y-2})...$ 構成的容器的容積顯然沒有 $(x,a_x)$ 與 $(y,a_y)$ 構成的容器的容積大。也就是說，我們可以直接將x右移，然後比較 $a_{x+1}$ 和 $a_y$ ，接著較小的高度對應的指針向中心移動，同時不斷比較構成的容器容積，取遍歷過程中的最大值即可。

演算法描述如下

class Solution {public: int maxArea(vector<int>& height) { int l=0; int r=height.size()-1; long long ans=0; while(l<=r){ ans = max(ans, (long long)(r-l)*(long long)min(height[l], height[r])); if(height[l]<height[r]) l++; else r--; } return ans; }};

當然之前只是直觀的描述了演算法，那麼正確性怎麼證明呢？

我們要證明左右指針一定同時經過了構成最大容積的兩條直線。

假設容器實際最大值在 $(x,a_{x})$ 和 $(y,a_{y})$ ，而且左指針剛經過了 $x$ 的時候右指針不經過 $y$ 。在這種情況下，注意到我們右指針在 $x$ 移動前一定不會經過 $y$ （除非是循環終止條件 $x==y$ ，這種情況顯然矛盾），這樣我們一定能在右指針抵達 $y$ 之前找到一個 $y$ 有 $a_{y} > a_{x}$ ，這樣 $x$ 才能繼續移動，右指針才有機會經過 $y$ 而不同時經過 $x$ 。但是此時 $(x,a_{x})$ 和 $(y,a_{y})$ 已經得到了一個更大的容器，與假設矛盾，所以正確性得證。

整體時間複雜度 $O(n)$ ，空間複雜度 $O(1)$

5 後記

妙啊！這個 $O(n)$ 的演算法是真的妙。

另外今天下午LeetCode伺服器掛了快一個小時（