首页 > 代码库 > leetcode:Container With Most Water
leetcode:Container With Most Water
题目
给定一系列整数代表在0,1,2,3...坐标点板的高度,求出在任意两个板之间能装水的最大截面积.
分析
首先,我们会想到遍历下每一个板,选取任意两个板,求出最大的,但是这个会超时,效率太低
其次,我们乐意想到在遍历的基础上优化,即有一个预测,这样可以在一定程度上提高效率,但是并不是太好,我试了下还
是不能过.
我们就要想,能不能遍历一遍就求出来.
1:left = 0, right =height.size();
2:如果left< right,则3,否则四
3:求出此时面积的大小,并判断左边和右边板的高度哪一个大,左边小于右边的话,left++;否则,right--;并判断是否
将Maxarea更新,返回2
4:结束,返回最大面积
穷举
class Solution { public: int maxArea(vector<int> &height) { int area,Maxarea,high; Maxarea = 0; for(int i=0;i<height.size();i++){ if(height[i]==0) continue; for(int j=0;j<i;j++){ area = (i-j)*(high=height[i]>height[j]? height[j]:height[i]); if(area>Maxarea) Maxarea = area; } } return Maxarea; } };预测优化
class Solution { public: int maxArea(vector<int> &height) { int area,Maxarea,high; Maxarea = 0; for(int i=0;i<height.size();i++){ if(height[i]==0) continue; int steplen = i - Maxarea/height[i]; for(int j=0;j<i&&j<=steplen;j++){ area = (i-j)*(high=height[i]>height[j]? height[j]:height[i]); if(area>Maxarea) Maxarea = area; } } return Maxarea; } };
双指针
class Solution { public: int maxArea(vector<int> &height) { int left = 0; int right = height.size() - 1; int area,Maxarea,high,step; Maxarea = 0; int flag; while(left<right){ area = (right-left)*(high=height[left]>height[right]? height[right]:height[left]); if(height[left]<height[right]) left++; else right--; if(area>Maxarea) Maxarea = area; } return Maxarea; } };
leetcode:Container With Most Water
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。