力扣 11 盛最多水的容器

作者 : 开心源码 本文共619个字,预计阅读时间需要2分钟 发布时间: 2022-05-13 共386人阅读

题意:给定一个数组,每一个元素代表容器壁的高度,两个元素的间距代表容器的宽度,找出两个数能组成成最多水的容器
比方:[1,5,1,4],当容器壁为5和4时盛水最多,最多的盛水为:Math.max(5, 4) * (3-1)= 6,其中3和1是4和5在数组中的索引

思路:

  1. 在数组的开始和结尾各设置一个指针;
  2. 指向数值较小的一边优先开始移动;
  3. 移动开始前先查看当前盛水能否比目前记录的最大值大,假如大则升级最大值;
  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 盛最多水的容器

发表回复