博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[LeetCode][Java] Container With Most Water
阅读量:5925 次
发布时间:2019-06-19

本文共 902 字,大约阅读时间需要 3 分钟。

题目:

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.

题意:

给定n个非负整数a1a2, ..., an, 每一个代表在坐标(iai)上的一点,连接(iai) and (i, 0)形成n条垂直线。找出两条垂线,和x坐标形成一个容器,使得这个容器包括的水最多。

注意:你不能够倾斜容器。

算法分析:

    两边夹的策略

    两个指标i j往中间走。每次计算i和j之间的面积。假设比眼下最大面积大。则更新最大面积,否则让两者之间较小的数的指标往前走。

    假设height[i] <= height[j],那么i++,由于在这里height[i]是瓶颈,j往里移仅仅会降低面积,不会再添加area。

    这是一个贪心的策略,每次取两边围栏最矮的一个推进,希望获取很多其它的水。

AC代码:

public  int maxArea(int[] height)     {    	int left=0;    	int right=height.length-1;    	int temwater;    	int res=0;    	while(left
res) res=temwater; if(height[left]

转载于:https://www.cnblogs.com/clnchanpin/p/6853463.html

你可能感兴趣的文章
南阳38--布线问题
查看>>
通过jsp请求Servlet来操作HBASE
查看>>
Learn Python 012: for loop
查看>>
安全试验资源
查看>>
系统问题
查看>>
StanFord ML 笔记 第六部分&&第七部分
查看>>
NFS服务搭建
查看>>
echarts雷达图点击事件 包含(2.x,3.85,4.02)测试
查看>>
spring boot 加载过程分析--ConfigurationClassPostProcessor
查看>>
[译] Fiber内幕:深入概述React新的协调算法
查看>>
app设计摘要
查看>>
Typescript 的成长环境
查看>>
转 C++STL之string
查看>>
demo06 webpack + babel7 + typescript
查看>>
eureka 服务实例实现快速下线快速感知快速刷新配置解析
查看>>
C# 给DateTime赋值正确方式
查看>>
html中子界面与父界面相互操作或传值
查看>>
转岗·空调工程师·自己动手拆空调记录
查看>>
SpringMVC_实现简单的增删改查
查看>>
spring_简介
查看>>