首页 > 代码库 > 每日算法之十:Container With Most Water
每日算法之十:Container With Most Water
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.
给定一个向量,其中的每个元素代表了高度,比如height[3] = 5,说明在坐标轴中在点3处存在高度为5的竖线,这样所有的元素就形成一个琴状的形状,最后要求的就是两条竖线之间的矩形形状最大的面积。最直觉的做法就是穷举,这样的复杂度是O(n2),显然还有更合适的方法,因为在这样的方法中有很多确定要小的面积也进行了计算。关于面积有两个变量,一个是横轴之间的距离,;另一个是两条竖轴之间的距离。我们可以固定其中一个变量,很显然,我们可以先取最远的两条竖线进行比较,然后使两个辅助指针逐渐缩小,取两个辅助指针中的较小的向中间移动。这样就可以是复杂度缩小到O(n).
class Solution { public: int maxArea(vector<int> &height) { int i = 0,j = height.size()-1; int temp,area = 0; while(i<j) { temp = (j - i)*min(height[i],height[j]); area = temp>area?temp:area; if(height[i]<height[j]) i++; else j--; } return area; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。