轻松一刻，算法求最大蓄水面积

一个有意思的题目，求最大蓄水面积
简单介绍一下，找到两个柱子，使其“蓄水”面积最大譬如

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

如果是直接暴力破解当然可以，两层for循环，组合所有可能，搞定
当然这肯定不是最好的方式，我们仔细思考一下，就会发现这个面积取决两个因素：长 * 宽
这不是废话吗！当这个“水池”的左右两个边分别是开始和结束的柱子，那么它的长最大了，水池的长度最大应该是这个数组的长度。我们设想两个指针，分别指向开始和结束这两个柱子，求得第一个面积，但这个面积可能不是最大的，因为宽度可能不够高，于是我们缩小长度（减一），寻找更高的宽度从而弥补长度带来的损失
关键是该如何寻找呢，回到例子，第一个柱子高度是1，最后一个柱子高度是7，整个面积的宽度受限于最小的高度（木桶效应），那么还有必要计算第一个柱子和其他的柱子之间的面积了吗？没有必要，因为第一个柱子无论和后面2-8个柱子里面哪一个柱子组合都不可能会超过这个面积了。所以，受限于最短柱子，后面无需再运算了。
所以如果想找到更高的，就右移动左边的指针，开始计算第二个柱子和最后一个柱子，然后继续抛弃其中较小的柱子，直达这两个指针相遇。
下面是我用go的简单实现，仅供参考

func maxArea(height []int) int {
	var result int
	for i,j := 0,len(height)-1; i < j;{
		result = maxInt(result, (j -i ) * minInt(height[i], height[j]))
		if height[i] < height[j]{
			i ++
		}else{
			j --
		}
	}
	return result
}

func maxInt(x, y int) int {
	if x >y {
		return x
	}
	return y
}

func minInt(x, y int) int {
	if x >y {
		return y
	}
	return x
}

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/u010278923/article/details/84847711
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2019-08-25 15:57:39
阅读 ( 1484 )
分类：算法

轻松一刻，算法求最大蓄水面积

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看