1. 题目
给定一个长度为 n n n 的整数数组 h e i g h t height height 。有 n n n 条垂线,第 i i i 条线的两个端点是 ( i , 0 ) (i, 0) (i,0) 和 ( i , h e i g h t [ i ] ) (i, height[i]) (i,height[i]) 。
找出其中的两条线,使得它们与 x x x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明:你不能倾斜容器。
示例 1:
输入:[1,8,6,2,5,4,8,3,7]
输出:49
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
示例 2:
输入:height = [1,1]
输出:1
提示:
- n = = h e i g h t . l e n g t h n == height.length n==height.length
- 2 < = n < = 1 0 5 2 <= n <= 10^5 2<=n<=105
- 0 < = h e i g h t [ i ] < = 1 0 4 0 <= height[i] <= 10^4 0<=height[i]<=104
2. 思路及代码实现(Python)
2.1 双指针
这里有一个很直接的方式,就是遍历所有的容器边界组合,一个个对比找到装水最多的,但是这样的算法复杂度为 O ( n 2 ) O(n^2) O(n2),那是否有办法缩减掉一些组合呢?使得我们并不需要遍历所有的组合也能找到容量最大的容器。
这个方法就是双指针,在列表的左右两端生成指针,不断地把指针向中间靠拢,能够覆盖所有地容器边界情况,但是每一次移动指针,都会缩减一部分边界组合,这里就有一个问题,到底需要移动哪个指针?假设有两个指针在列表的 i , j i,j i,j 位置,其中, h e i g h t [ i ] < h e i g h t [ j ] height[i] < height[j] height[i]<height[j],不论我们移动哪一边的指针,容器的长都会减小,且容器的高取决于最矮的边界,因此,对于左指针(较矮)而言,不会有包含左指针的组合且容量还大于当前组合的情况了,因此左指针可以移动。
例如:[3,>2,6,8,3,2,4<],假设左指针在2,右指针在4,此时的容器容量为 5 × 2 = 10 5\times 2=10 5×2=10,显然,不论我们如何移动右指针,只要左指针还是2的位置,那右指针的值可能比4高,或者比4低甚至比2低,但新容器的长都会小于5,且高不会高于2(取边界的较小值),因此固定左指针2之后的容器容量不会再高于10,此时可以舍弃左指针的位置,向右移动。
依次类推,左右指针不断把较小值向中间推移,最终得到的较大容量即为总体最大的容量。此时,由于指针只移动了 n n n 次,因此算法时间复杂度为 O ( n ) O(n) O(n),而移动指针的过程只记录指针位置和当前最大值,空间复杂度为 O ( 1 ) O(1) O(1)。
class Solution:
def maxArea(self, height: List[int]) -> int:
l, r = 0, len(height) - 1
ans = 0
while l < r:
area = min(height[l], height[r]) * (r - l)
ans = max(ans, area)
if height[l] <= height[r]:
l += 1
else:
r -= 1
return ans
执行用时:169 ms
消耗内存:26.77 MB文章来源:https://www.toymoban.com/news/detail-820663.html
参考来源:力扣官方题解文章来源地址https://www.toymoban.com/news/detail-820663.html
到了这里,关于LeetCode_11_中等_盛最多水的容器的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!