11.盛最多水的容器

直接的思路O(n^2)，超时

class Solution:
    def maxArea(self, height: List[int]) -> int:
        max_val = None
        for i in range(len(height)-1):
            for j in range(i+1, len(height)):
                if max_val is None or (j-i) * min(height[i], height[j]) > max_val:
                    max_val = (j-i) * min(height[i], height[j])
        return max_val

进行优化，考虑如果第i个柱子不是前i个柱子里最高的，则第i个柱子肯定不是最优解的左侧则舍弃，缩小查询的范围

class Solution:
    def maxArea(self, height: List[int]) -> int:
        test = {}
        max_val = None
        max_height = None
        for i in range(len(height)):
            for index in test.keys():
                val = (i - index) * min(height[i], test[index])
                if max_val is None or val > max_val:
                    max_val = val
            if max_height is None or height[i] > max_height:
                test[i] = height[i]
                max_height = height[i]
        return max_val

仍然超时，考虑查询的范围可以继续缩小，可以维护一个升序的待测试数组test,test[i]是一个tuple，分别是index和对应的height，那么第二层for循环 的时候就可以顺序循环，如果循环到某个柱子的高度已经高于当前柱子，那么就不用继续遍历test数组了，从而进一步缩小查询范围

class Solution:
    def maxArea(self, height: List[int]) -> int:
        test = []
        max_val = None
        for i in range(len(height)):
            for j in range(len(test)):
                val = (i - test[j][0]) * min(height[i], test[j][1])
                if max_val is None or val > max_val:
                    max_val = val
                if test[j][1] >= height[i]:
                    break
            if not test or height[i] > test[-1][1]:
                test.append((i,height[i]))
        return max_val

但是依然超时，做到这一步，也就证明了必须要O(n)的算法了。看了题解 着重看一下正确性证明这一部分。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        i, j = 0, len(height)-1
        max_val = None
        while i < j:
            val = (j-i) * min(height[i], height[j])
            if max_val is None or val > max_val:
                max_val = val
            if height[i] < height[j]:
                i += 1
            else:
                j -= 1
        return max_val

其实一开始看见题目中的2 <= n <= 10^5就应该直接想双指针的方案，O(n^2)的就不应该尝试浪费时间。关键就在于双指针的正确性证明

评论