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 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.
Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
public class Solution {
public int maxArea(int[] height) {
int lpoint = 0, rpoint = height.length - 1;
int area = 0;
while (lpoint < rpoint) {
area = Math.max(area, Math.min(height[lpoint], height[rpoint]) * (rpoint - lpoint));
if (height[lpoint] > height[rpoint])
rpoint--;
else
lpoint++;
}
return area;
}
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
Java
class Solution {
public int maxArea(int[] height) {
int l = 0;
int r = height.length - 1; // idx values left and right
int le = height[l];
int re = height[r]; // element value for left and right
int thisLe = 0;
int thisRe = 0; // for comparisons with previous elements
int max = Math.min(le, re) * (r - l); // initial max area
while(l < r) {
le = height[l]; // left elemnt
re = height[r]; // right element
if (le < re) {
thisLe = le; // for comparing it with next elements
// find next elemnt towards right that is greater than this left element
while (l < r && thisLe >= height[l]) l++;
// finf max area
max = Math.max(max, Math.min(height[l], height[r]) * (r - l));
} else if (le > re) {
thisRe = re; // for comparing it with next elements
// find next elemnt towards left that is greater than this right element
while(l < r && thisRe >= height[r]) r--;
// find area
max = Math.max(max, Math.min(height[l], height[r]) * (r - l));
} else {
// if both elements are same
// calc area for them
// and consider for elements towards each other
max = Math.max(max, Math.min(height[l], height[r]) * (r - l));
l++;
r--;
// find max area for this new elements
max = Math.max(max, Math.min(height[l], height[r]) * (r - l));
}
}
return max;
}
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
- 36.
- 37.
- 38.
class Solution:
def maxArea(self, height: List[int]) -> int:
i = 0
j = len(height) - 1
max_area = 0
while i < j:
m = height[i] if height[i] < height[j] else height[j]
m = m * (j-i)
max_area = max_area if max_area > m else m
if height[j] > height[i]: i+=1
else: j-=1
return max_area
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
class Solution {
public:
int maxArea(vector<int>& height) {
int i = 0;
int j = height.size() - 1;
int max = -1;
int area = 0;
int h = 0;
while (i < j) {
if (height[i] < height[j])
h = height[i];
else
h = height[j];
area = (j - i) * h;
if (max < area)
max = area;
if (height[i] < height[j])
i++;
else
j--;
}
return max;
}
};
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
原网站版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15740726/5540627
