11. 盛最多水的容器

2024-01-09 12:18:59

题目:

给定一个长度为?n?的整数数组?height?。有?n?条垂线,第?i?条线的两个端点是?(i, 0)?和?(i, height[i])?。

找出其中的两条线,使得它们与?x?轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明:你不能倾斜容器。(废话)

【解题思路】

盛水最多的容器是个非常经典的题了,思路也比较简单,想象一下,要使得两端挡板夹住的水能够达到最多,那么决定权必然是在两端挡板中最短的那个,既然如此,那我们就可以从最外围两个挡板开始不断向内找,每次找都记录下两个挡板所夹住的水的最大值,而且,两端挡板向内缩要分三种情况:1. 左端挡板比右端短,此时移动左端向右走一步;2. 右端挡板比左端短,此时移动右端向左走一步;3. 两端挡板一样长,此时两端同时向内走一步;这是因为,最短的挡板才决定能盛多少水,所以我们每次都要移动最短的那一侧。

上述其实是双指针的解题方法,下面上代码:

def maxArea(self, height: List[int]) -> int:
        if len(height) == 2:
            return min(height)
        left, right = 0, len(height)-1
        res = 0
        while left < right:
            s = min(height[left], height[right]) * (right - left)
            res = max(s, res)
            if height[left] > height[right]:
                right -= 1
            elif height[left] < height[right]:
                left += 1
            else:
                left += 1
                right -= 1
        return res

文章来源:https://blog.csdn.net/qq_36583400/article/details/135473524
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。