链接：https://leetcode.cn/problems/container-with-most-water/
11. 盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
我自己的暴力解法
class MySolution
{
public:
int maxArea(std::vector<int> &height)
{
if (0 == height.size())
{
std::cout << "error,input error size is 0!" << std::endl;
return 0;
}
int max_area_value = 0;
int max_area_temp = 0;
for (int i = 0; i < height.size(); ++i)
{
for (int j = i; j < height.size(); ++j)
{
max_area_temp = std::min(height[i], height[j]) * (j - i);
std::cout << "i = " << i << " j = " << j << ",max_area_temp = " << max_area_temp << std::endl;
if (max_area_temp > max_area_value)
{
max_area_value = max_area_temp;
}
}
}
return max_area_value;
}
};虽然也能求出来，但是肯定超时，效率很低。
官方题解
看了官方题解，自己也重新写了一遍如下：
class Solution {
public:
int maxArea(vector<int>& height) {
if (0 == height.size())
{
std::cout << "error,input error size is 0!" << std::endl;
return 0;
}
int max_area_value = 0;
int max_area_temp = 0;
int left_index = 0;
int right_index = height.size() - 1;
for (int i = 0; i < height.size(); ++i)
{
if (left_index >= right_index)
{
break;
}
max_area_temp = std::min(height[left_index], height[right_index]) * (right_index - left_index);
if (max_area_temp > max_area_value)
{
max_area_value = max_area_temp;
}
if (height[left_index] < height[right_index])
{
left_index++;
}
else
{
right_index--;
}
}
return max_area_value;
}
};官方剪短版本。代码写的很剪短优美。
class Solution {
public:
int maxArea(vector<int>& height) {
int i = 0, j = height.size() - 1, res = 0;
while(i < j) {
res = height[i] < height[j] ?
max(res, (j - i) * height[i++]):
max(res, (j - i) * height[j--]);
}
return res;
}
};