首页 > 代码库 > [leetcode]Container With Most Water
[leetcode]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 linei 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.
基本思路:
此题最简单的想法是遍历每种可能。时间复杂度是O(n^2);
更好的一个思路是每次改变容器左右壁的短板,希求能通过提升短板的高度来找到更大的容量。可以结合代码理解思路。
代码:
int maxArea(vector<int> &height) { //C++ int begin = 0 ; int end = height.size()-1; int max = 0, tmpArea; while(begin < end){ tmpArea = (end-begin)*((height[begin]>height[end])?height[end]:height[begin]); if(tmpArea > max){ max = tmpArea; } if(height[begin] > height[end]) end--; else begin++; } return max; }
[leetcode]Container With Most Water
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。