Python 中水量最多的容器

pythonserver side programmingprogramming更新于 2025/10/25 11:56:17

假设我们有一组 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 := length of arr – 1, ans := 0
while low < high
- if 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]))