其他
【LeetCode】(No.011) 盛最多水的容器
击上方“Ahab杂货铺”,选择“置顶公众号”
技术分享第一时间送达!
NO.11 盛最多水的容器
原题:
给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明:
你不能倾斜容器,且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
示例:
输入: [1,8,6,2,5,4,8,3,7]输出: 49
双指针法:
1.定义两个指针,left和right,初始时,指向首部和尾部
2.计算两个指针之间的面积area1 = min(height[left],height[right])*(right-left)
3.maxArea = Max(maxArea,area1)
4.height[left]和height[right],谁小谁往里面走
# 记录当前最大容量的面积
max_area = 0
# 记录最左边的下标
left = 0
# 记录右边的下标
right = len(height) - 1
# 当右边下标大于左边下标的时候循环
while right > left:
#当前循环中最大的容量面积,
使用max方法比较上次的
# max_area和此次的容量面积,取最大值
# min(height[left], height[right]) * (right - left)
# 取左边和右边的高当中的最小值,
# 标right-left为宽,两者相乘为最大面积
max_area = max(max_area,
min(height[left],height[right]) * (right - left))
# 判断哪条高小,小的那边下标进行操作
if height[right] > height[left]:
left += 1
else:
right -= 1
return max_area
当然还有最简单的粗暴的双循环,之前做过太多类似的题目就不具体介绍。
欢迎您的点赞和分享
▲长按关注此公众号