📌 给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
说明:你不能倾斜容器。
双指针往中间靠拢
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
defmax_area_towards_center(arr): """ 数组:一开始就将 left bar 和 right bar 设置到最左和最右 慢慢收敛,因为宽度已是最大,只需要控制高度即可 """ l, r = 0, len(arr) - 1 ans = 0 while l < r: area = min(arr[l], arr[r]) * (r - l) ans = max(ans, area) if arr[l] <= arr[r]: l += 1 else: r -= 1 return ans
max_area_towards_center([1,2,3,4,5,6,7,8,9,10])
使用 for 循环
1 2 3 4 5 6 7 8 9 10 11 12 13 14
defmax_area_2_loop(arr): """ 数组:枚举所有元素,双重 for 循环,找出 area 最大的 缺点,时间复杂度比较高 """ area_max = 0 for i inrange(len(arr)): for j inrange(1, len(arr)): area = (j-i) * min(arr[i], arr[j]) area_max = max(area_max, area)