MENU

Catalog

乘最多水的容器问题与双指针法

April 4, 2020 • 题解,Python

最近在力扣上看到一个题目,链接在这:乘最多水的容器

题目

给你 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。
经过思考以后呢,我想出了两个办法:

第一个是使用遍历的方法去暴力的将所有的结果进行计算然后再输出最大值
代码如下:

class Solution:
    def maxArea(self, height: List[int]) -> int:
        waters=[]
        for i in range(len (height)):
            value1=height[i]
            for j in range(len(height)):
                value2=height[j]
                box_height=min(value1,value2)
                length=abs(i-j)
                water=length*box_height
                waters.append(water)
        return max(waters)

第二个方法呢便是使用双指针法,一次性扫描,得出答案

height=[1,8,6,2,5,4,8,3,7]
res=[]
left=0
right=len(height)-1
while right != left:
    area=min(height[left],height[right])*(right-left)
    res.append(area)
    if height[left] > height[right]:
        right-=1
    else:
        left+=1
max_area=max(res)
    

第一个解法面对较小的数值时,是没有什么问题的,但是面对较大的数据时,便会带来较大的计算压力O(n2)
第二个解法只用扫描一遍,便可以得出答案是一种较为省时的方案O(n)

而对于双指针法,可以这样理解:力扣官方题解

作者:NorthCity1984
出处:https://grimoire.cn/acm/container-with-most-water.html
版权:本文《乘最多水的容器问题与双指针法》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任

Last Modified: March 7, 2022