题目:
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 = 0i = 0j = len(height) - 1while i < j:vol = (j - i) * min(height[j], height[i])if vol >= max_vol:max_vol = volif height[j] > height[i]:i += 1else:j -= 1return 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) - 1max_capacity = 0while i < j:cur_capacity = (j - i) * min(height[j], height[i])# 容积受到短板影响, 前后指针比较,移动较短的指针if height[i] < height[j]:i += 1else:j -= 1max_capacity = max(cur_capacity, max_capacity)return max_capacity
