11. Container With Most Water（medium)

02-12

題目：

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.

這題的關鍵是找到那個恰好使兩條線圍成面積最大的狀態。

假設左邊那條線是第i條，右邊那條線是第j條，很容易發現一個事實：

在i的左邊沒有比他更高的線/在j的右邊也沒有比他更高的線，也就是說只需要把i和j從兩邊向中間移動即可，遇到更高的線就更新自己的值。

但是這樣有一個問題，就是儘管i的左邊沒有比他更高的線，但i的右邊可能有，也就是說不知道移動到哪個線合適。

所以對於可能的情況都要判斷一下（每更新一個i,j）

class Solution {public: int maxArea(vector<int>& height) { if (height.empty()){ return 0; } int leftIndex = 0; int rightIndex = height.size() - 1; int maxLeft = leftIndex; int maxRight = rightIndex; int max = min(height[leftIndex], height[rightIndex]) * (rightIndex - leftIndex); int area; while (leftIndex < rightIndex) { if (height[leftIndex] > height[rightIndex]){ rightIndex--; if (height[rightIndex] > height[maxRight] && leftIndex < rightIndex){ maxRight = rightIndex; area = min(height[maxLeft], height[maxRight]) * (maxRight - maxLeft); if (max < area){ max = area; } } } else{ leftIndex++; if (height[leftIndex] > height[maxLeft] && leftIndex < rightIndex){ maxLeft = leftIndex; area = min(height[maxLeft], height[maxRight]) * (maxRight - maxLeft); if (max < area){ max = area; } } } } return max; }};