Container With Most Water
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 the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the area of water it contains is maximal.
Constraints:
- 2 <= height.length <= 10^5
- 0 <= height[i] <= 10^4
Examples:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Solutions
Two Pointers
The idea is to start with two pointers, one at the beginning and one at the end of the array. We calculate the area of water that can be trapped between the two lines, and update the maximum area if necessary. We then move the pointer of the shorter line towards the other end, because the area of water that can be trapped is limited by the height of the shorter line.
int maxArea(vector<int>& height) {
int max = 0, left = 0, right = height.size() - 1;
while (left < right) {
int h = min(height[left], height[right]);
int w = right - left;
max = max > h * w ? max : h * w;
if (height[left] < height[right]) left++;
else right--;
}
return max;
}Follow-up:
What if we want to find the maximum area of water that can be trapped between three lines?
