【LeetCode】11.盛最多水的容器
题目要求
解题思路
首先我们想到的肯定是依次遍历选出最大的值，这样的时间复杂度为O（N^2）。而我们观察可以的得知，一旦取得左右边界，那么中间的值一定会小于边界的值，这样我们就可以减少枚举次数，将时间复杂度降至O（N）
代码实现
class Solution
{
public:
int maxArea(vector<int>& height)
{
int left=0,right=height.size()-1;
int h=height[left]>height[right]?height[right]:height[left];
int w=right-left;
int sum=h*w;
while(left<right)
{
if((height[left]>height[right]?height[right]:height[left])*(right-left)>sum) sum=(height[left]>height[right]?height[right]:height[left])*(right-left);
height[left]>height[right]?right--:left++;
}
return sum;
}
};