首页 > 代码库 > [Leetcode] Container With Most Water ( C++)
[Leetcode] Container With Most Water ( C++)
题目:
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 };
[Leetcode] Container With Most Water ( C++)