力扣 11 盛最多水的容器
题意:给定一个数组,每一个元素代表容器壁的高度,两个元素的间距代表容器的宽度,找出两个数能组成成最多水的容器
比方:[1,5,1,4],当容器壁为5和4时盛水最多,最多的盛水为:Math.max(5, 4) * (3-1)= 6,其中3和1是4和5在数组中的索引
思路:
- 在数组的开始和结尾各设置一个指针;
- 指向数值较小的一边优先开始移动;
- 移动开始前先查看当前盛水能否比目前记录的最大值大,假如大则升级最大值;
- 记录开始的指针值;
- 移动指针直到找到比开始的值大的新值,由于在移动的过程中,宽度在不断减小,只有当新移动到的容器壁比最开始的容器壁高,才可能会比之前记录的值大;
思想:首尾指针法
复杂度:时间O(n),空间O(1)
class Solution { public int maxArea(int[] height) { int len = height.length; int s = 0; int e = len - 1; int res = 0; while(s<e) { if(height[s]<=height[e]) { res = Math.max(height[s] * (e-s), res); int temp = height[s]; while(s<e && height[s] <= temp) { s++; } } else { res = Math.max(height[e] * (e-s), res); int temp = height[e]; while(s<e && height[e] <= temp) { e--; } } } return res; }}说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 力扣 11 盛最多水的容器
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 力扣 11 盛最多水的容器