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.
Notice
You may not slant the container.
Have you met this question in a real interview?
YesExample
Given [1,3,2]
, the max area of the container is 2
.
LeetCode上的原题,请参见我之前的博客Container With Most Water。
解法一:
class Solution {
public:
/**
* @param heights: a vector of integers
* @return: an integer
*/
int maxArea(vector<int> &heights) {
int res = , i = , j = heights.size() - ;
while (i < j) {
res = max(res, min(heights[i], heights[j]) * (j - i));
heights[i] < heights[j] ? ++i : --j;
}
return res;
}
};
解法二:
class Solution {
public:
/**
* @param heights: a vector of integers
* @return: an integer
*/
int maxArea(vector<int> &heights) {
int res = , i = , j = heights.size() - ;
while (i < j) {
int h = min(heights[i], heights[j]);
res = max(res, h * (j - i));
while (i < j && h == heights[i]) ++i;
while (i < j && h == heights[j]) --j;
}
return res;
}
};