## 盛最多的水 Container With Most Water 原

叶枫啦啦

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;
}
}

### 叶枫啦啦

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

dby_freedom
2018/09/07
0
0

2016/12/12
7
0

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学习笔记

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 颜色模式

10
1

12
0