LeetCode 11 - 盛最多水的容器

written at 20/06/01

题目描述

给你 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。
示例：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

朴素： 最naive的解法肯定是枚举所有的情况，即枚举左右端点。这样的操作时间复杂度为
分析： 我们从两端往中间搜去寻找两边的木桩的时候，是间隔不断在变短的过程，若是想让搜的过程中朝着有用的方向前行，那么必须两端中最短的那根木桩被替换。基于此有了一种搜索思路即对于两端短的那一段去往中间搜索寻找比他长的下一木桩。
正确性证明： 假若已知最优解是。那么我们这套搜索流程是否一定会寻找到它？答案是一定的。因为若是最优解，则，即左右端点之外的木桩都比他们要短。且即当前处木桩的值比的所有木桩值都高。 证明：假设其中一个不满足，即，则最优解将被更新为，于前提假设最优解是不满足。
所以按照我们上述的搜索方法，必定可以找出最优解，且其时间复杂度为

代码

class Solution(object):
    def cal_vol(self, height_l, height_r, length):
        return min(height_l, height_r) * (length)
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        l, r = 0, len(height)-1
        max_vol = self.cal_vol(height[l], height[r], r-l)
        while l < r:
            if height[l] < height[r]:
                l_t = l + 1
                while l_t < r and height[l_t] <= height[l]:
                    l_t += 1
                l = l_t
            else:
                r_t = r - 1
                while l < r_t and height[r_t] <= height[r]:
                    r_t -= 1
                r = r_t
            max_vol = max(max_vol, self.cal_vol(height[l], height[r], r-l))
        return max_vol