题目:
011.盛水最多的容器
思路:
双指针,一个置于开始i,一个置于末尾j。max_vol记录当前最大容量。
容量大小总是受短的一边影响,短板效应;所以要找到比当前max_vol更大的容量,短板所在的指针须移动。
class Solution:
def maxArea(self, height: List[int]) -> int:
# vol = (j - i) * min(height[j], height[i])
# max(vol)
max_vol = 0
i = 0
j = len(height) - 1
while i < j:
vol = (j - i) * min(height[j], height[i])
if vol >= max_vol:
max_vol = vol
if height[j] > height[i]:
i += 1
else:
j -= 1
return max_vol
class Solution:
def maxArea(self, height: List[int]) -> int:
# area = min(a_j, a_i) * (i - j)
# min(a_j, a_i) * abs(a_i - a_j)
i, j = 0, len(height) - 1
max_capacity = 0
while i < j:
cur_capacity = (j - i) * min(height[j], height[i])
# 容积受到短板影响, 前后指针比较,移动较短的指针
if height[i] < height[j]:
i += 1
else:
j -= 1
max_capacity = max(cur_capacity, max_capacity)
return max_capacity