题目大意

利用x轴作底，给出一个数组，两个任意的竖直线段作杯壁，何时盛水最多。

解题思路

  • 可以直接for循环i，j遍历，那复杂度就是O(n^2)

  • 复杂度为O（n）的思想是贪心原理，这种方法背后的思路在于，两线段之间形成的区域总是会受到其中较短那条长度的限制。此外，两线段距离越远，得到的面积就越大。

我们在由线段长度构成的数组中使用两个指针，一个放在开始，一个置于末尾。 此外，我们会使用变量 maxareamaxarea 来持续存储到目前为止所获得的最大面积。 在每一步中，我们会找出指针所指向的两条线段形成的区域，更新 maxareamaxarea，并将指向较短线段的指针向较长线段那端移动一步。

代码

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

总结