LEETCODE 11. 盛最多水的容器
题目描述
给定 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
。
示例:
输入: [1,8,6,2,5,4,8,3,7]
输出: 49
题目地址:
https://leetcode-cn.com/problems/container-with-most-water/solution/dong-hua-yan-shi-11-sheng-zui-duo-shui-de-rong-qi-/
题解
求容器能够容纳水的最大值,其实就是求矩形的最大面积。
我们定义两个指针(指向上图中红色的柱子)来代表两个柱子,然后这两个指针都向中间移动,每次移动的时候都计算一下当前的面积,并保存下来,等到两个指针相遇时(即两个指针都指向同一个柱子时)遍历结束,就可以求的最大的矩形面积。
怎么计算矩形面积呢?
比如这个数组:
[1,8,6,2,5,4,8,3,7]
下标1
的值是8
,下标8
的值是7
。通过值和下标这两个维度就可以计算矩形了。
将右边下标-
左边下标,就能得出矩形的长度,然后再计算 max(
下标1
的值,下标8
的值)
得到高度,有了长度和高度就可以得出面积了。
时间复杂度:O(n)
空间复杂度:O(1)
java代码:
class Solution { public int maxArea(int[] height) { if(height==null) { return 0; } //定义两个指针,分为位于最左边和最右边 int i = 0; int j = height.length-1; int res = 0; //两个指针不断像中间移动,每迭代一次都会计算矩形的最大面积 while(i<j) { int tmp = Math.min(height[i],height[j]); res = Math.max(res,tmp*(j-i)); if(height[i]<=height[j]) { ++i; } else { --j; } } return res; } }
python代码:
class Solution(object): def maxArea(self, height): """ :type height: List[int] :rtype: int """ if not height: return 0 # 定义两个指针,分为位于最左边和最右边 i = 0 j = len(height)-1 res = 0 # 两个指针不断像中间移动,每迭代一次都会计算矩形的最大面积 while i<j: tmp = min(height[i],height[j]) res = max(res,tmp*(j-i)) if height[i]<=height[j]: i += 1 else: j -= 1 return res
(全文完)
10 次阅读