【LeetCode】11. Container With Most Water

题目大意：选两个线加上x轴组成容器，装下更多的水。

Given n non-negative integers a₁, a₂, …, a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) 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.

height[i]的值就是板子i的高度。

解析：

这里需要注意的是，容量 = 底 * 高。

这里假设我们从”底”最长开始，到 “底” = 0

“高”必须是增加的，否则就没有增加。

所以，我们设定一个left和right…

可以发现取的最大值的时候，left左边的高度肯定小于left，right右边的高度肯定小于right…

当然这句话没有什么意义，只是说明高度需要慢慢增加。

然后left = 0，right = n-1 (假设n个嘛)

if height[left] < height[right] :

left += 1

else :

right -=1

这里是因为，

当left的高度较小的时候，left值应该右移以尽量取得更大值来增大容量。

当right 高度较小的时候，right应该左移以尽量取得更大值来增大容量。

解释：

当 height[left] < height[right] 时，

left 右移取到一个更小的，无妨，前面的值我已经记录过了。

left右移取到一个更大值，容量可能变为较大的容量。

right左移取到一个更小值，容量肯定更小

right左移取到一个更大值，容量也肯定更小

当height[left] > height[right] 时，也是这个道理。

代码如下：

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if len(height) < 2:
            return 0
        
        left = 0
        right = len(height) - 1
        
        ans = 0
        while left < right :
            ans = max(min(height[left], height[right]) * (right - left) , ans)
            if height[left] < height[right] :
                left += 1
            else :
                right -= 1
                
        return ans

class Solution(object):

def maxArea(self, height):

"""

:type height: List[int]

:rtype: int

"""

if len(height) < 2:

return 0

left = 0

right = len(height) - 1

ans = 0

while left < right :

ans = max(min(height[left], height[right]) * (right - left) , ans)

if height[left] < height[right] :

left += 1

else :

right -= 1

return ans

说实话个人还试过双重循环，最高点向两边查找…都失败了(⊙﹏⊙)b。

心疼自己。

【LeetCode】11. Container With Most Water

Tagged on: LeetCode Python