盛最多水的桶

盛最多水的桶

题目描述：

        给定一个非负整数序列：序列中依次表示高度。在坐标系内画出这么多条线（ 线的端点为(i, hi) 和 (i, 0)），在其中寻找两条线使得两条线所构成的容器可以容纳最多的水。

分析：

        

方法一： 暴力解法

        1.遍历左右边

        2.找出所有面积

        3.取最大值

方法二： 双指针法

        1.设置两个指针，分别对应左右两边

        2.计算当前所对应的容器容量

        3.移动较短的指针向内移动

Python代码（暴力解法就不展示了，下面的是双指针解法）：

def maxArea(height):
    l, r = 0, len(height) - 1
    ans = 0
    while l < r:
        area = min(height[l], height[r]) * (r - l)
        ans = max(ans, area)
        if height[l] <= height[r]:
            l += 1
        else:
            r -= 1
    return ans


list = [1, 6, 2, 8, 7, 2, 2, 8, 9, 5]
r = maxArea(list)
print(r)

可以对上面稍微进行改进：

def maxArea(height):
    i, j = 0, len(height) - 1
    maxArea = 0
    while i < j:
        h, w = min(height[i], height[j]), j - i
        maxArea = max(maxArea, h * w)  # record before the move
        curr = min(height[i], height[j])
        if height[i] < height[j]:
            while height[i] <= curr and i < j:
                i += 1
        else:
            while height[j] <= curr and i < j:
                j -= 1
    return maxArea


list = [1, 6, 2, 8, 7, 2, 2, 8, 9, 5]
r = maxArea(list)
print(r)