[Leetcode] Container With Most Water ( C++)

浏览数：43 / 时间：2015年06月08日

题目：

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.

Tag:

Array; Two Pointers

体会：

1. 这道题我觉得是双指针的一个创新用法。之前的双指针都是一主一辅，辅助的那个不断去探测下一个，然后主要的那个会根据探测结果做出相应动作，比如 Merge Sorted Array ,这道题的双指针两个人是同等重要性，根据其他的判定条件来决定下一次移动谁。

2. 这道题之所以是双指针是同等位置，也可以从另外一个角度来感受，就是要知道左边那条线“和”右边那条线的位置，两个都是未知的，都是要确定的。

3. 回到题目上，O(N)的解法。代码很简单，可是能想到不容易。（我也是炒的别人的思路）。为什么每次是那样移动指针呢？假设h[left] < h[right]，那么在计算过第一次面积之后，假设还有更大的面积，则一定不可能是line left。这是因为，如果另外选择一条线left next 来和line left围面积的话，(right - left) > (next - left)，即长方形的长度会变短，然后长方形高度不会比heght[left]更高。所以面积一定不会更大，所以只有移动right的位置才可能会找到更大面积。

 1 class Solution {
 2 public:
 3     int maxArea(vector<int> &height) {
 4             int left = 0;
 5             int right = height.size() - 1;
 6             int result = 0;
 7             int area = 0;
 8             while (left < right) {
 9                 if (height[left] < height[right]) {
10                     area = (right - left) * height[left++];
11                 } else {
12                     area = (right - left) * height[right--];
13                 }
14                 if (area > result) {
15                     result = area;
16                 }
17             }
18             return result;
19     }
20 };