leetcode-11-盛最多水的容器
题解:
核心逻辑:
(1)如果左边的边界高度低于右边的边界高度,则右边界左移只会缩小容器盛水面积;所以只能左边界右移才可能增大容器盛水面积。即 if height(left)<height(right) ---->left+=1。
(2)如果左边的边界高度高于右边的边界高度,则左边界右移只会缩小容器盛水面积,所以只能右边界左移才可能增大容器盛水面积。即 if height(left)>height(right)---->right-=1
(3)综上,移动较短的一边才能使容器的盛水面积增大。
实现:
1、初始化两个指针,分别指向数组开头和结尾。即start=0,end=len(height)-1。
2、初始化一个空列表ls_res用来存储每次移动边界后的容器面积。
3、进入while循环进行指针移动。循环条件:start<end。
4、计算当前start和end之间的容器面积:(end-start)*min(height(end),height(start))。并将该面积存入ls_res。
5、如果height(start)<height(end),则右移start。即start+=1。
6、如果height(start)>height(end),则左移end。即end-=1。
7、循环结束,获取ls_res的最大值就是容器盛水最大面积。