Python 中盛水最多的容器

假设我们有一组 n 个非负整数 a1、a2、…、an，每个值表示坐标 (i, a[i]) 处的一个点。存在 n 条垂直线，使得第 i 条线的两个端点位于 (i, a[i]) 和 (i, a[0])。我们需要找到两条线，它们与 x 轴一起形成一个容器，我们的目标是找到两列，其中水的体积最大。因此，如果数组类似于 [1,8,6,2,5,4,8,3,7]，则结果将是

在阴影部分，高度为 7，有 7 个部分，因此总面积实际上是 7 * 7 = 49。这是输出结果。

为了解决这个问题，我们将遵循以下步骤

  • low := 0，high := arr 的长度 – 1，ans := 0
  • 当 low < high 时
    • 如果 arr[low] < arr[high]：min_h := height[low] 且 min_ind := low
    • 否则 min_h := height[high] 且 min_ind := high
    • ans := (high – low) * min_h 和 ans 中的最大值
    • 如果 low + 1 = min_ind + 1，则将 low 增加 1，否则将 high 减小 1
  • 返回 ans

示例

让我们看看以下实现，以便更好地理解 -

 在线演示

class Solution(object):
   def maxArea(self, height):
      low = 0
      high = len(height) - 1
      ans = 0
      while low < high:
         if height[low]<height[high]:
            min_height = height[low]
            min_height_index = low
         else:
            min_height = height[high]
            min_height_index = high
         ans = max(((high - low) ) * min_height,ans)
         if low+1==min_height_index+1:
            low+=1
         else:
            high-=1
      return ans
ob1 = Solution()
print(ob1.maxArea([1,8,6,2,5,4,8,3,7]))

输入

[1,8,6,2,5,4,8,3,7]

输出

49

更新于: 2020 年 4 月 27 日

336 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告