盛水最多的容器

Leetcode Link: 11. 盛最多水的容器 - 力扣（LeetCode）

题目

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

解法一

思路： 暴力冲了, 两个 for 搞定, 超时

题解：时间 $O(N^2)$, 空间 $O(1)$

class Solution:
    def maxArea(self, height: List[int]) -> int:
        res = 0
        for l in range(len(height)):
            for r in range(l+1, len(height)):
                res = max(res, self.get_volume(height, r, l))
        return res
 
    def get_volume(self, height, r,  l):
        return min(height[r], height[l]) * (r-l)

解法二

思路：双指针，有点贪心的味道

本题的双指针为相向而行的双指针。

开始从 0 到 len (height)-1 的范围上，我们计算出一个体积，在这个基础上，我们用什么方法，可能（这里不是一定）获得一个更大的体积？

把小的那个边往中间移动一下看看，可能会得到更大的体积，这里是可能。似乎有一些贪心的味道在里面。 我们保留长边不动，一直移动短边，找到最大体积。

简言之

在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽底边宽度 -1变短：

• 若向内 移动短板 ，水槽的短板 min(h[i],h[j]) 可能变大，因此下个水槽的面积 可能增大 。

• 若向内 移动长板 ，水槽的短板 min(h[i],h[j]) 不变或变小，因此下个水槽的面积 一定变小 。

我也是突然感觉来了想的思路...

题解的证明一

题解的证明二

题解：时间$O(N)$, 空间$O(1)$

class Solution:
    def maxArea(self, height: List[int]) -> int:
        res = 0
        for l in range(len(height)):
            for r in range(l+1, len(height)):
                res = max(res, self.get_volume(height, r, l))
        return res
 
    
    def get_volume(self, height, r,  l):
        return min(height[r], height[l]) * (r-l)