网站内置字体,无锡微信公众号开发,广州网络科技有限公司,软件开发是吃青春饭的吗本节将数组与坐标轴共同组成一个容器,通过改变容器的两个端点使容器装的水最多,容器两个端点不断移动可以通过左右指针算法解决. 问题描述:
给定两个非负整数k1,k2...km每个数代表坐标中的一个点(i,ki).在坐标内绘制m条垂线,垂直线i的两个端点分别为(i,k1)和(i,0)找出其中的两…本节将数组与坐标轴共同组成一个容器,通过改变容器的两个端点使容器装的水最多,容器两个端点不断移动可以通过左右指针算法解决. 问题描述:
给定两个非负整数k1,k2...km每个数代表坐标中的一个点(i,ki).在坐标内绘制m条垂线,垂直线i的两个端点分别为(i,k1)和(i,0)找出其中的两条线,使他们与x轴共同构成的容器可以容纳最多的水.
思路解析:
一个容器的最终盛水量和两个因素有关一个是左右两个边界的高度;二是左右两边的距离.变量如下:
height变量:表示输入的高度数组
left表示:表示容器左边界的高度,最初指向数组的第一个元素
right变量:表示容器的右边界高度,最初指向数组的最后一个元素
res变量:表示最终返回的最大盛水量.res的初始值为0
完整代码如下:
def maxArea(self, height): # 定义一个函数maxArea接收两个参数self如果是类的方法和height柱子高度的列表res 0 # 初始化结果res为0res用来记录遍历过程中找到的最大面积left 0 # 初始化left指针指向数组的开始right len(height) - 1 # 初始化right指针指向数组的末尾while(left right): # 当left指针小于right指针时循环继续res max(res, min(height[left], height[right]) * (right - left)) # 计算当前左右指针所形成的矩形面积并更新resif(height[left] height[right]): # 如果左边柱子的高度小于右边柱子的高度left 1 # 将left指针向右移动寻找可能的更高柱子else: # 否则right 1 # 将right指针向左移动寻找可能的更高柱子return res # 返回计算得到的最大面积
