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

Arnab Chakraborty

更新於: 2020 年 4 月 27 日

336 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習