盛最多水的容器

1. 题目描述

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

2. 思路

1. 思路一
   • 暴力
   • 其实就是计算长方形的面积（j-i）*min(a[i], a[j])，取出其中的最大者
   • 遍历穷举即可
2. 思路二
   • 双指针
   • 左指针为最左边，右指针为最右边，计算当前面积
   • 取短板往中间靠拢
   • 解释为什么需要移动短板而不是长板
     • 无论是移动短板或者长板，我们都只关注移动后的新短板会不会变长
     • 而每次移动的木板都只有三种情况，比原短板短，比原短板长，与原短板相等；
     • 如向内移动长板，对于新的木板：
       • 1.比原短板短，则新短板更短。
       • 2.与原短板相等或者比原短板长，则新短板不变。
     • 所以，向内移动长板，一定不能使新短板变长。

3. 实现

3.1. 暴力

func maxArea(height []int) int {
	res := 0

	for i := 0; i < len(height); i++ {
		for j := i + 1; j < len(height); j++ {
			res = Max(res, (j-i)*min(height[i], height[j]))
		}
	}
	return res
}

3.2. 双指针（夹逼法）

func maxArea(height []int) int {
    left := 0
    right := len(height)-1
    res := 0
    for left < right {
        if height[left] < height[right] {
            res = max(res, (right-left)*height[left])
            left++
        } else {
            res = max(res, (right-left)*height[right])
            right--
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

4. 参考

• 盛最多水的容器（双指针法，易懂解析，图解） - 盛最多水的容器 - 力扣（LeetCode）