原题链接https://leetcode.com/problems/container-with-most-water/找出在n条垂直于x轴的线中能够组成的最大容器面积的两条线容器不能倾斜n的最小值为2.解题思路1.暴力破解设起始点为i终点为j找到能使面积最大的i和j。classSolution:defmaxArea(self,height:List[int])-int:max_area0foriinrange(len(height)):forjinrange(len(height)-1,i,-1):cur_areamin(height[i],height[j])*(j-i)ifcur_areamax_area:max_areacur_areareturnmax_area测试的时候发现这个方法虽然可行但是超时了…试图用动态规划来解决但是好像也不是很可行, 运行的时候栈溢出了。最后看了答案感觉答案里给出的这个思路还是有点难想到的。设置两个指针i和j分别代表第一条线和最后一条线。比暴力搜索优化的地方在于当计算完当前面积的时候比较一下i和j的大小如果i j, i i 1如果i j 的话j j -1。这样做的原因是每次i或者j向内移动 j - i都会随之变小面积也会变小所以需要保留相对高的高度来抵消j - i的变小然后自己按照答案的思路实现了一下classSolution:defmaxArea(self,height:List[int])-int:max_areai0jlen(height)-1whileij:cur_areamin(height[i],height[j])*(j-i)ifcur_areamax_area:max_areacur_areaifheight[i]height[j]:i1else:j-1returnmax_area有一个意外的发现在python里用max函数比写if else的条件语句还要慢···
原题链接https://leetcode.com/problems/container-with-most-water/找出在n条垂直于x轴的线中能够组成的最大容器面积的两条线容器不能倾斜n的最小值为2.解题思路1.暴力破解设起始点为i终点为j找到能使面积最大的i和j。classSolution:defmaxArea(self,height:List[int])-int:max_area0foriinrange(len(height)):forjinrange(len(height)-1,i,-1):cur_areamin(height[i],height[j])*(j-i)ifcur_areamax_area:max_areacur_areareturnmax_area测试的时候发现这个方法虽然可行但是超时了…试图用动态规划来解决但是好像也不是很可行, 运行的时候栈溢出了。最后看了答案感觉答案里给出的这个思路还是有点难想到的。设置两个指针i和j分别代表第一条线和最后一条线。比暴力搜索优化的地方在于当计算完当前面积的时候比较一下i和j的大小如果i j, i i 1如果i j 的话j j -1。这样做的原因是每次i或者j向内移动 j - i都会随之变小面积也会变小所以需要保留相对高的高度来抵消j - i的变小然后自己按照答案的思路实现了一下classSolution:defmaxArea(self,height:List[int])-int:max_areai0jlen(height)-1whileij:cur_areamin(height[i],height[j])*(j-i)ifcur_areamax_area:max_areacur_areaifheight[i]height[j]:i1else:j-1returnmax_area有一个意外的发现在python里用max函数比写if else的条件语句还要慢···
