题目描述
11. 盛最多水的容器 - 力扣(LeetCode)https://leetcode.cn/problems/container-with-most-water/
思路分析
这题就是典型的是一道很经典的面试题,最优的解法是双指针,但很多人在第一次看到这题的时候很难想到用双指针来解(比如我)。好了,话不多说上解法:文章来源:https://www.toymoban.com/news/detail-620306.html
首先我们设两个left和right分别指向height数组的头和尾。而容纳的水就相当于是面积,面积就等于:两个指针指向的数字中较小值 ∗ 指针之间的距离。那么接下来我们就要通过移动最右指针来不断比较,最终获取最大面积。即走一趟,求最大。而由于起初left在最左端,right在最右端,它们之间的距离就是最大的。所以无论left和right怎么移动,都是向中间移动,那么它们之间的距离一定是在不断减小的,所以我们需要每次移动left和right位置中的较小的那个指针。因为距离一定是减1的,所以我们每次舍弃掉较小的一个高度。(其实,这也可以说是一种贪心的思想)文章来源地址https://www.toymoban.com/news/detail-620306.html
我的题解
class Solution {
public:
int maxArea(vector<int>& height)
{
int left = 0;
int right = height.size() - 1;
int max_area = 0;
while(left < right)
{
// 走一趟,求出最大
int high = std::min(height[left], height[right]);
int cur_area = (right - left) * high;
max_area = std::max(max_area, cur_area);
// 谁小让谁走,一样小的,无所谓
if(high == height[left])
left++;
else
right--;
}
return max_area;
}
};
到了这里,关于LeetCode_11. 盛最多水的容器的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!