[題目] Given n non-negative integers a₁, a₂, …, a_n, where each rePResents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) 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.

[中文翻譯] 給定n個非負整數a₁，a₂，…，a_n，其中每個表示坐標(i, a_i)處的點。 繪制n條垂直線，每條線的兩個端點為(i, a_i)和(i, 0)。 找到兩條線，它們與x軸一起形成一個容器，使得容器包含最多的水。

注意：您不能傾斜容器，n至少為2。

[解題思路] 樸素的解法，枚舉兩條線的組合，然后計算出面積最大的一組，效率為O(n²)。

但實際上，有很多組合是可以不需要枚舉的。 如圖，紅色的兩條線，是當前枚舉的組合，綠色區域是容器能包含的水。那么，在兩條紅線中間的線，任意一條與短的那條紅線形成的新的組合，所能包含的水一定不會超過綠色區域。因為短的那條紅線決定了最高的高度，而寬度不會比綠色區域的寬度更寬。因此，假設已考慮過兩條紅線之外的黑線，那么之后的枚舉過程中，短紅線已經可以移除，因為存在短紅線的組合已經不可能是最優解。 至此，我們可以得到一個O(n)的算法，用兩條線表示當前枚舉到的組合，初始時是最左和最右兩條線，然后依次將短的一條移除，用內部最靠近它的線代替，得到新的枚舉組合。這樣的枚舉，可以保證不會遺漏最優解，因為沒有枚舉到的組合都不會是最優解。然后計算這些枚舉到的組合中，面積最大的一組即可。

[C++代碼]