力扣学习笔记——11. 盛最多水的容器

最多水的容器"/>

力扣学习笔记——11. 盛最多水的容器

链接：/

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;}
};