山西中交建设工程招标有限公司网站百度平台订单查询

本节将数组与坐标轴共同组成一个容器,通过改变容器的两个端点使容器装的水最多,容器两个端点不断移动可以通过左右指针算法解决.

问题描述:

给定两个非负整数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为0，res用来记录遍历过程中找到的最大面积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  # 返回计算得到的最大面积