【LeetCode最详尽解答】11-盛最多水的容器 Container-With-Most-Water

欢迎收藏Star我的Machine Learning Blog:https://github.com/purepisces/Wenqing-Machine_Learning_Blog。如果收藏star, 有问题可以随时与我交流, 谢谢大家！

链接：

• 11-盛最多水的容器

直觉

这个问题可以通过可视化图表来理解和解决。

通过图形化这个问题，可以简化解决过程。我们可以使用双指针技术来解决它。起初，左指针设置在数组的起点，右指针设置在数组的终点。目标是找到最大的可能面积，这个面积受指针指向的较短高度的限制。面积可以通过公式 min(height[left], height[right]) * (right - left) 计算。容器的高度受较短的两个高度之一限制。

为了最大化面积，我们应该移动指向较短高度的指针。这是因为移动指向较高高度的指针不会有助于找到更大的面积，因为容器的高度仍然会受较短高度的限制。具体来说，新高度将是 min(height[left], height[new_right])，它将小于或等于之前的较短高度，并且间隔距离也会缩小。因此，如果左指针指向较短高度，我们将其向右移动。相反，如果右指针指向较短高度，我们将其向左移动。

方法

1. 初始化两个指针：左指针在数组起点，右指针在数组终点。
2. 初始化一个变量 res 来存储最大面积。
3. 使用公式 res = max(res, min(height[left], height[right]) * (right - left)) 来计算面积并更新 res。
4. 移动指向较短高度的指针以尝试找到更大的面积。
5. 设置提前停止条件：设 h 为数组中的最大高度。如果 (right - left) * h 小于 res，则意味着不可能找到更大的面积，因此我们可以跳出循环。

复杂度

• 时间复杂度：
  $$O(n)$$
  • 我们只用两个指针遍历数组一次，时间复杂度为线性。
• 空间复杂度：
  $$O(1)$$
  • 无论输入大小如何，我们只使用了常量空间。

代码

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        l = 0
        r = len(height) -1
        h = max(height)
        res = 0
        while l < r:
            if (r-l) * h <= res:
                break
            res = max(res, min(height[l],height[r]) * (r-l))
            if height[l] <= height[r]:
                l+=1
            elif height[l] > height[r]:
                r-=1
        return res