【LeetCode】（No.011） 盛最多水的容器
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当然还有最简单的粗暴的双循环，之前做过太多类似的题目就不具体介绍。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2018-10-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
