阿里终面：如何才能盛下最多的水？

作者丨涛歌依旧

来源丨经授权转自  涛歌依旧（ID：ai_taogeyijiu_2021）

大家好，我是涛哥。又到周末了，愿大家开心。

今天不聊复杂的技术问题，来看一道阿里巴巴的终面题目。有趣，而且有一定难度。

编程求max{|i-j|*min{a[i], a[j]}}的值，其中a是正整数数组，i和j的区间为[0, n-1].

初次看到这个题目时，可能处于懵圈状态，怎么有min又有max呢？到底如何下手？

我一直的观点是：既然要找工作，那就要做万全准备，LeetCode题型又岂能不刷？

问题转化

很显然，这是非常典型的“盛水容器问题”，我来翻译一下，原题等价于如下的问题：

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

输入：a = [1, 8, 6, 2, 5, 4, 8, 3, 7]

输出：49

解释：图中垂直线代表输入数组a =  [1, 8, 6, 2, 5, 4, 8, 3, 7]，在此情况下，容器能够容纳水(表示为蓝色部分)的最大值为49.

常规解法

最容易想到的就是暴力枚举法，因为i和j的可能性是有限组合，所以暴力算法能得到结果，但无法通过阿里巴巴的面试。

所以，我们的思路自然很容易转到常见的动态规划上来，但是，想了很久也没有找到递推的关系式，所以放弃动态规划。

双指针法

我们可以采用双指针，分别指向头尾，计算出盛水值。然后向中间搜索，尝试找出更大的盛水可能性。为什么会有这种思路呢？因为木桶理论告诉我们：

对于两块确定的盛水挡板而言，盛水的多少是由短板决定的。所以很显然知道，在向中间搜索时，从短板侧向中间移动指针，才有可能产生更大盛水值。

既然算法思路清楚了，那接下来的程序就很简单了。我们用现在非常流行的Go语言来编程，并在LeetCode上完成了测试和验证。Go语言的代码如下：

func maxArea(a []int) int { n := len(a)
if n < 2 { return 0 }
if n == 2 { return min(a[1], a[0]) }
max := min(a[n - 1], a[0]) * (n - 1)
i := 0 j := n - 1
for i < j { if a[i] < a[j] { i++ }else { j-- }
area := min(a[i], a[j]) * (j - i) if area > max { max = area } }
return max}
func min(x, y int) int { if x < y { return x }
return y}测试用例和结果如下：

可以看到，当输入的正整数组数 a = [1, 8, 6, 2, 5, 4, 8, 3, 7]时，盛水的最大值是49，具体图示如下：

这个题目有一定难度，如果终面没做对这道题，那基本就和阿里巴巴无缘了。最后，祝愿大家找到满意的工作。

点分享

点点赞

点在看