前言
刷水题证明还会语法
正文
问题来源
本问题来自leetcode上的11题。
问题描述
给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
示例 1
输入:
[1,8,6,2,5,4,8,3,7]
输出: 49
分析：
正解的复杂度应该是 O(n) 的。
我们可以举个简单的例子，假设数组是 [2, 3, 4, 5, 4, 3]，那么最长的子数组一定只有一个，即取全部元素，这样能装的水的数量是 2 * 5 。接下去我们的子元素，长度一定是会变小的，有两种情况，为 [2, 3, 4, 5, 4] 和 [3, 4, 5, 4, 3]。我们来看 [2, 3, 4, 5, 4]，这种情况下，显然比取全部元素求得的结果 10 要小，为什么这么说？因为两者的基准都是按 2 来算的，但是取全部元素长度大。
似乎有点眉目了，再来看 [2, 3, 4, 5, 4, 3] 这个原始的数组，从中找出一个子数组，如果以 2 为子数组最左的元素，那么这个子数组求解的值（即装水的量），不可能比 [2, 3, 4, 5, 4, 3] 这个原始数组求到的 10 要大了，有木有？！因为该子数组装水的基准，是不可能比 2 大了的。
这样，我们似乎可以用一点点贪心去解这道题，一步步缩小子数组的大小。
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func maxArea(height []int) int {
left := 0
right := len(height) - 1
maxa := 0
for left <= right {
maxa = max((right-left)*min(height[left],height[right]),maxa)
if height[left] > height[right] {
right--
} else {
left++
}
}
return maxa
}
优化一下
func maxArea(height []int) int {
var currentMax int
l, r := 0, len(height)-1
for(l != r && r > l){
currentArea := 0
if(height[l] > height[r]){
currentArea = height[r] * (r-l)
r--
} else {
currentArea = (r-l)*(height[l])
l++
}
if(currentArea > currentMax){
currentMax = currentArea
}
}
return currentMax
}
总结：
水一水
结语
不要懒，多看多写。
