首页 > 代码库 > [Leetcode] Container With Most Water ( C++)

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

题目:

Given n non-negative integers a1a2, ..., an, where each represents a point at coordinate (iai). n vertical lines are drawn such that the two endpoints of line i is at (iai) 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 };

 

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