题目描述

给定 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 次阅读