力扣hot100 C++(自用05)

思路:双指针移动,左指针指向数组一个元素;右指针指向数组最后一个元素;比较左右指针指向数字,对应较小的数字对应位置指针向中间方向移动一格,每一次移动前与移动后的面积比较,只保留比较后最大的面积;当左右指针指向的位置一样时就结束。
为什么最优解在这个过程里面,因为宽度减小:当高度大的一侧移动时面积一定变小,当高度小的一侧移动时面积可能变大或者变小或者不变;
class Solution {
public:
int maxArea(vector<int>& height) {
int l=0;//初始左指针位置
int r=height.size()-1;//初始右指针位置
int s=0;//初始化面积大小
while(l<r)
{
int h=min(height[l],height[r]);//计算面积时的高度
int w=r-l;//计算宽
s=max(h*w,s);//保留每次最大的面积
if(height[l]>=height[r])//右指针对应数字较小,右指针向中间移动一格;左右指针对应数字一样大小右指针向中间移动一格(也可以是左指针移动)
{
r=r-1;
}
else//左指针对应数字较小,左指针向中间移动一格
{
l=l+1;
}
}
return s;
}
};
更多推荐
所有评论(0)