LeetCode第11题: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) 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个非负的整数a1到an,ai每个代表i处的高度,(i,ai)和(i,0)是线段i的两个端点,所有任意两个线段i可以和x轴组成一个容器,找出能装最多水的容器。注意:不能倾斜容器。

思路

这道题所求的容积和容器下边长度(两个线段的横坐标距离)和侧边最小长度有关(类似木桶效应)。
所以容积 = abs(i2 – i1) * min(ai1, ai2),我们要找出的就是用那两条线段做边界时,这个容器最大,求出这个最大的容积。

怎么在保证效率的情况下找出这个最大的容积呢?通过查看discuss,发现这个题有一个巧妙的思路:设定两个“游标”,开始分别指向最左和最右。如果一边的线段较低,那么这一边的“游标”就可以向里移动,直到两个“游标”相遇,这样,复杂度就从暴力方法的O( n^2 )变成了O(n)。
为什么可以这样呢?我们可以举个反例:假如最左边线段高度为2,最右边为5,两线段相距为10,如果这时我们向里移动的是右边的线段,那么新容器的容积只会比原来小,而不会比原来大,所以,这样的尝试是没有必要的。

代码

Python

发表评论

电子邮件地址不会被公开。 必填项已用*标注