刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/container-with-most-water/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

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

找出其中的两条线，使得它们与 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 == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

思路

两个边不断往中间移动尝试找最大值，我觉得很多人都是能想到的

但是最关键的就是，怎么移动？如何确保移动后不会错过最大值？

这个只靠想可能会有点难想，不如写下来面积公式，就比较清晰了：

max = min(height[left], height[right]) * (right-left)

假设此时 height[left] > height[right]

• 此时如果向右移动 left, 那么 height[left] 可能变大、变小、不变，但是 min(height[left], height[right]) 一定不会变大， 因为即使 height[left] 变大了，height[right] 没变。
• 此时如果向左移动 right，那么 height[right] 可能变大，min(height[left], height[right]) 就有可能会变大

所以，移动 height[left], height[right] 中更小的一方即可~

至此，上代码

代码

func maxArea(height []int) int {
	left, right := 0, len(height)-1
	maxA := 0
    // 不能相等
	for right > left {
        // 尝试更新最大面积
		temp := (right - left) * min(height[right], height[left])
		if temp > maxA {
			maxA = temp
		}
        // 移动小的，尝试增大两个边的较小值
		if height[right] < height[left] {
			right--
		} else {
			left++
		}
	}
	return maxA
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}