【LeetCode10】盛最多水的容器

今日挑战

给定 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

先思考一下，后面我会给出一个解题思路～?

图来自网络

这道题还是采用双指针的办法去解决，我们把其叫做左指针和右指针。

1 ）初始化两个指针，分别在数组两端，左端的叫左指针i，右端的叫右指针j，初始化一个res用来记录当前的水槽面积。

2 ）指针逐步往中间收缩，判断哪个指针比较"矮"，也就是指针所对应的数值较小那个，就将那个指针往里缩一位（如果说右指针，则向右移动，如果说左指针，则向左）。

这里解释一下：

• 因为水槽面积由左右指针的最"矮"的那个高度以及底面长度决定的，而每次往里收缩，底面长度会变小，如果移动"高"的那个指针，即便遇到了更高的指针，水槽高度还是由"矮"的指针决定，而底面长度又变小了，所以得到的水槽面积，永远比一开始的要小。
• 所以，"破局之法"就是把"矮指针”往里移动，寻求其他更高的指针。

3 ）直到两个指针相遇，程序停止，返回res的最大值。

Python实现：

def maxArea( height):
    i, j, res= 0, len(height) - 1, 0
    while i < j:
        if height[i] < height[j]:
            res = max(res, height[i] * (j - i))
            i += 1
        else:
            res = max(res, height[j] * (j - i))
            j -= 1
    return res

扩展一下：若要找面积最小的水槽，应该将两指针设在height中心，向两边扩散，每轮都扩散长板对应指针。

? 配图角色背景介绍

Hawkeye，他是在马戏团长大的孤儿，因超一流的箭术被神盾局指挥官尼克·弗瑞慧眼识珠，加入复仇者联盟。鹰眼侠行动迅速果敢，个性低调沉稳，出招百发百中，极其擅长狙击。在漫威漫画故事中，鹰眼侠曾与黑寡妇有绯闻。在电影《雷神》里，鹰眼曾被安排在高空射杀索尔。 鹰眼,真名“克林特·巴顿”(Clint Barton)，他是一个在马戏团长大的孤儿，擅长弓箭，在看到钢铁侠后受到启发，自己也弄来一套行头化身成“鹰眼侠”，但不幸的是，他总会被人们误当成罪犯。克林特不是“复仇者联盟”的最初成员，但后来遇到“黑寡妇”以后加入了这一组织。 鹰眼凭借自身高超的射术加入复仇者联盟，尽管拥有超强的射击技术加上精良的装备但是依旧是肉体凡胎，在复仇者联盟中处于辅助型的地位。