Skip to content

Latest commit

 

History

History
24 lines (12 loc) · 1.15 KB

File metadata and controls

24 lines (12 loc) · 1.15 KB

装最多水的容器

问题描述

给一组二维坐标的点,x从1开始递增,y是随机的正整数,每个点有垂直横坐标的线段,求两条线围成的容器哪个装的水更多。

input [1,1]

output 1

个人思路

假如给两个点(x1,y1) (x2,y2)就是求min(y1,y2) * (x2-x1)最大;随着测试的进行,有三个思路。

  • 首先就是暴力破解法,两层循环就可以求出最大的面积;但是在提交答案时出现Time Limit Exceeded, 即时间复杂度太大,为O(n^2)

  • 接下来就是改进了,对内层循环进行修改,不要傻傻的去一个一个比对,从两端分别往中间找,找到面积比目前大的两个候选答案,然后选中面积最大那个;这个算法对部分数据确实有很大提升,但是遇上[1,2,3..]这样的极端情况,复杂度又变成了O(n^2)

  • 如果要复杂度降为O(n),则肯定只能遍历一遍,所以最终的方法是:维持两个指针,从两端分别往中间扫描,哪端最短就移动它的指针,这样一遍下来就得出了结果。

答案思路

答案给出的就是我的1,3答案,思路是一致的。