题意:
方法一:
双指针+贪心
思路:双指针,l , r 分别指向左右边界。
class Solution { public: int maxArea(vector<int>& height) { int l=0,r=height.size()-1; int res=0; while(l<r){//循环 res=max(res,(r-l)*min(height[l],height[r]));//维护面积的最大值 if(height[l]<height[r]){//移动高度值小的一方 l++; }else{ r--; } } return res; } };
时间复杂度:空间复杂度:
方法二:
暴力(超时)
思路:暴力,二重循环枚举区间的左右边界。
并维护最大值。
class Solution { public: int maxArea(vector<int>& height) { int n=height.size(); int res=0; for(int i=0;i<n;i++){//二重循环遍历区间左右边界 for(int j=i+1;j<n;j++){ res=max(res,(j-i)*min(height[i],height[j]));//维护最大值 } } return res; } };
时间复杂度:
空间复杂度: