首页 > 代码库 > 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 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.
这个题嘛,不会!网上的解题思路有点像从一个有序数组中找出两个数使其和为给定数,都是从两边往中间扫描。
设置两个指针i,j分别指向序列首尾,算出面积后将高度较小的那个指针往中间移动,重新计算面积。当i >= j时结束返回。
代码如下:
class Solution { public: int maxArea(vector<int> &height) { int len_height = height.size(); if(len_height == 0)return 0; int j = len_height - 1; int i = 0; int area = 0; while(i < j) { area = max(area,(j - i) * min(height[i],height[j])); if(height[i] > height[j]) j--; else i++; } return area; } };
总结+牢骚:智商真的不够用。我是绝对想不到这样的方法的。也不知道牛人们是怎么想出这种方法的。要是您看到了这篇博客并且有一些想法您能指点一下我吗?多谢!
Leetcode:Container with most water 最大蓄水量
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。