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.
题目大意
以数组中的高度为木桶的边，两个高度和x周构成木桶，问最多装多少水？
思路
贪心
参考代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class
Solution {
public
:
int
min(
int
val1,
int
val2)
{
return
val1 < val2 ? val1 : val2;
}
int
maxArea(vector<
int
> &height) {
int
size = height.size();
int
left = 0, right = size - 1;
int
max = min(height[right], height[left]) * (right - left);
while
(left < right)
{
if
(height[left] < height[right])
++left;
else
--right;
int
tmp = min(height[right], height[left]) * (right - left);
if
(tmp > max)
max = tmp;
}
return
max;
}
};
|
本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/p/3649426.html，如需转载请自行联系原作者
