Skip to content

Latest commit

 

History

History
 
 

010. Container With Most Water

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

这道题着实想了好一阵子。

首先难在理解题意,这个返回值到底代表什么含义?

我开始总以为是相邻的两个line组成的水池,根据短板效应,也就成了类似找最大值的问题。后来察觉到不对,才发现题目并没有说什么相邻。恍然大悟,应该是求任意两条线形成大最大面积。

这该怎么解决?再长的线如果距离不够长,那也是白搭。如何能够综合考虑?

已经很晚的时候,我才灵机一动,如果从最长距离开始呢?左边是beg,右边是end,然后总体向里挪动。在挪动过程中不断比较,记住最大值。

但问题的关键在于怎么移动?

我开始想岔了,总想着要有最大面积的话,需要更长的边才行,于是觉得应该分别与里面的边比,如果遇到更长的,才往里挪动。结果发现这样根本挪不动。谁也无法保证里面就会比外面长。能比的只有 beg 和 end 这两个边。谁小,谁就应该往里面挪动。

这样,几乎就不会有什么遗漏的面积了。

于是,最后一个循环就搞定了,代码异常的简洁。