题目：
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.
大致意思如下：
有（1,a1) (2,a2)....(n,an)几个点，现在向x轴做垂线，其中两条垂线与所夹的一段x轴形成一个凹槽，可作为容器盛水，问盛水的最大的体积为多少？如下图：
解题：
我首先的想法是两个for循环嵌套，嗯，比较蠢，代码如下：
class Solution {public: int maxArea(vector& height) {
int contain = 0;
int temp = 0;
for(int i = 0; i < height.size() - 1; ++i)
{
for(int j = i + 1; j < height.size(); ++j)
{
temp = (height[i] <= height[j]) ? height[i] : height[j];
temp = temp * (j - i);
contain = (temp > contain) ? temp : contain;
}
}
return contain;
}
};
submission后奇迹出现了，49个testcase通过48个，然而，最后一个爆了，time limit exceed，我认为应该是太蠢，效率太低，然后爆掉了，毕竟两个for嵌套～
于是，在我看了其他大神的攻略后，发现自己果然蠢，这个题可以这么想：
1. 每次计算体积时一定以最短长度作为高
2. 如果左边低于右面的话，右边的横坐标越大越好
本着以上两点，我们可以用两个计数器，i初始为最左边，j初始为最右边，if height[i] < height[j], 那么就非常开心了，因为在这种情况下，此时一定体积最大（
因为高一定，此时最长），那么接下来我们就可以进行i右移一位了，反过来情况下，j就要左移一位了，代码如下：
class Solution {public: int maxArea(vector& height) {
int contain = 0;
int temp = 0;
int i = 0;
int j = height.size() -1 ;
if (height.size() == 2)
contain = (height[0] < height[1]) ? height[0] : height[1];
else {
while(i < j)
{
if (height[i] <= height[j])
{
temp = height[i] * (j - i);
contain = (temp > contain) ? temp : contain;
i++;
}
else
{
temp = height[j] * (j - i);
contain = (temp > contain) ? temp : contain;
j--;
}
}
}
return contain;
}
};
嗯～通过了，虽然only beats 29.18% cpp 且代码有点冗余，但这个思路先记下咯～
网友评论