leetcode - 盛最多水的容器

leetcode: 盛最多水的容器

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

示例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

---

这一题我在草稿纸上比比划划好久才搞清楚逻辑，首先，乍一看n个非负整数里面找到最大面积需要暴力遍历一遍，但是遍历是最没办法的办法–它极有可能超时，所以我们需要找到它的规律

对于面积的计算应该是底的长度和最短的高的乘积

然后如何找到这两条边就是我们的关键了，我们需要两个边，所以我们最好从左右两边最远的位置开始找，不断找到更大值才是题目关键，从短的一边开始找，因为高的一边无论怎么找计算的边都是短边，那么面积只会更小，所以我们不断从找更高的边并更新最大面积值，这就是这一题的灵魂所在了

捋清楚了我们就上代码

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        cleft = 0
        cright = len(height) - 1
        s = min(height[cleft], height[cright]) * (cright - cleft)
        ss = 0
        while cright > cleft:
            if height[cleft] > height[cright]:
                cright -= 1
            else:
                cleft += 1
            ss = min(height[cleft], height[cright]) * (cright - cleft)
            if s < ss:
                s = ss

        return s

也许会有人疑惑是否在这样的遍历中会错过最大值，我们可以分析一下,我们还是看看大佬的比我分析得好多了

https://leetcode-cn.com/problems/container-with-most-water/solution/shuang-zhi-zhen-fa-zheng-que-xing-zheng-ming-by-r3/

另外，实际上在左右两边相等时应该还要有一点考量，但是既然过了那就算了= =

今天开始锻炼身体，可能，这就是淬体吧= =