LeetCode:11. Container With Most Water

这一题 是要求求容器的最大面积，其中高度由数组中的数字表示，长度为两个数的下标距离。

这题，我是直接用的暴力法，超时了，借鉴了其他人的解题思路。

采用类似快排算法的思路，进行从两侧开始扫描，我们知道快排能够明显降低时间，如果用暴力法，当给定一个很大的数组时，就会花费很长时间。

class Solution:
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        # 设置左右下标
        l = 0
        r = len(height) - 1
        maxV = 0
        while l <= r:     # 当未来到中间时
            if height[l] <= height[r]:      # 左边的高度较低时 此时将其作为盛水容器的高度
                markV = (r - l)*height[l]
                l += 1
            else:
                markV = (r - l)*height[r]   # 右边的高度较低时 此时将其作为盛水容器的高度
                r -= 1
            maxV = max(markV, maxV)         # 获取最大面积值
        return maxV

下面也给出了暴力法的求解 

def test1(height):
    '''

    :param hegiht: type list[int]
    :return: int
    '''
    max = 0
    length = len(height)
    markV = 0
    maxV = 0
    for i, ele1 in enumerate(height):
        for j, ele2 in enumerate(height):
            if i < length -1-j and markV < height[length-1-j] :
                if markV != 0 and height[length-1-j]<=ele1:
                    markV = height[length-1-j]    # 高
                else:
                    markV = min(ele1, height[length-1-j])
                dist = length -1 -j -i
                if maxV < markV * dist:
                    maxV = markV * dist
                # 减少时间
                if height[(i+length-1-j)//2]<markV and  (i+length-1-j)//2+1 == length-1-j:
                    break
    return maxV