文档章节

盛最多的水 Container With Most Water

叶枫啦啦
 叶枫啦啦
发布于 2017/08/25 16:58
字数 411
阅读 7
收藏 0

问题:

Given n non-negative integers a1a2, ..., an, where each represents a point at coordinate (iai). n vertical lines are drawn such that the two endpoints of line i is at (iai) 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 and n is at least 2.

解决:

【注】题目的意思是,数组中的每个数对应一条线段的长度,索引对应x坐标,两个索引可以组成一个底部的宽,高度就是前面所说的线段的长度,而既然是要盛水,高度就是两个线段中较短的一个

① 暴力解决,超时。

class Solution {
    public int maxArea(int[] height) {
        int area = 0;
        for (int i = 0;i < height.length ;i ++ ) {
            for (int j = i + 1;j < height.length ;j ++ ) {
                area = Math.max(area,getArea(j - i,Math.min(height[i],height[j])));
            }
        }
        return area;
    }
    public int getArea (int x,int y){
        return x * y;
    }
}

② 因为数组下标i是有序的,使用双指针分别从左右两端向中间移动,如果height[i] < height[j],left左移(这时右侧的面积值可能会大于当前值),否则,right右移。

class Solution {//12ms
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;
        while(left < right){
            int area = (right - left) * Math.min(height[left],height[right]);
            if(maxArea < area) maxArea = area;
            if(height[left] < height[right]) left ++;
            else right --;
        }
        return maxArea;
    }
}

③ 进化版

public class Solution { //7ms
    public int maxArea(int[] height) {
        int maxArea = 0;
        int left = 0;
        int right = height.length - 1;
        while(left < right){
            if(height[left] > height[right]){
                if(maxArea < height[right] * (right - left))
                    maxArea = height[right] * (right - left);
                right --;
            }else{
                if(maxArea < height[left] * (right - left))
                    maxArea = height[left] * (right - left);   
                left ++;
            }
        }
        return maxArea;
    }
}

© 著作权归作者所有

叶枫啦啦
粉丝 14
博文 583
码字总数 400448
作品 0
海淀
私信 提问
leetcode-11 Container With Most Water 盛最多水的容器

title: "leetcode-11 Container With Most Water 盛最多水的容器" 我的博客 https://zszdata.com/2019/03/09/count-primes/ Container With Most Water 给定 n 个非负整数 a1,a2,...,an,......

sz88888
04/10
0
0
LeetCode 11. Container With Most Water

原题: Given n non-negative integers Note: You may not slant the container and n is at least 2. The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this ca......

dby_freedom
2018/09/07
0
0
容纳最多的水

原题   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 ......

一贱书生
2016/12/12
7
0
拿什么拯救你,太湖!

江苏无锡部分地区自来水发臭 市民抢购纯净水 2007年05月30日 扬子晚报   [扬子晚报网消息] "我们震泽新村的自来水怎么都是臭的啊?""我是曹张新村的居民,家里的自来水都是臭的。"昨天上午...

阮一峰
2007/06/12
0
0
leetcode -eleven: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......

Endeavour
2015/08/11
35
0

没有更多内容

加载失败,请刷新页面

加载更多

nginx学习笔记

中间件位于客户机/ 服务器的操作系统之上,管理计算机资源和网络通讯。 是连接两个独立应用程序或独立系统的软件。 web请求通过中间件可以直接调用操作系统,也可以经过中间件把请求分发到多...

码农实战
55分钟前
5
0
Spring Security 实战干货:玩转自定义登录

1. 前言 前面的关于 Spring Security 相关的文章只是一个预热。为了接下来更好的实战,如果你错过了请从 Spring Security 实战系列 开始。安全访问的第一步就是认证(Authentication),认证...

码农小胖哥
今天
8
0
JAVA 实现雪花算法生成唯一订单号工具类

import lombok.SneakyThrows;import lombok.extern.slf4j.Slf4j;import java.util.Calendar;/** * Default distributed primary key generator. * * <p> * Use snowflake......

huangkejie
昨天
11
0
PhotoShop 色调:RGB/CMYK 颜色模式

一·、 RGB : 三原色:红绿蓝 1.通道:通道中的红绿蓝通道分别对应的是红绿蓝三种原色(RGB)的显示范围 1.差值模式能模拟三种原色叠加之后的效果 2.添加-颜色曲线:调整图像RGB颜色----R色增强...

东方墨天
昨天
10
1
将博客搬至CSDN

将博客搬至CSDN

算法与编程之美
昨天
12
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部