11 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 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.
The Idea: Apply a greedy approach. Being with the widest lines (start and end) to first optimize the width. Then move
leftor rightiterators, depending on whether or not it supports a height greater than the previous. In other words, ignore smaller heights until a larger one is found. An otherwise smaller height would be that the supported area will be smaller than the previous.Complexity: O(n) time and O(1) space
int maxArea(vector<int>& heights) {
int left = 0, right = heights.size() - 1;
int max_water = 0;
while (left < right) {
int h = min(heights[left], heights[right]);
max_water = max(max_water, h * (right - left));
while (heights[left] <= h && left < right)
left++;
while (heights[right] <= h && left < right)
right--;
}
return max_water;
}
Last modified 4yr ago