网站首页 返回列表
像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。

leetcode基础算法学习之maxArea

18-10-23 09:36:07 云丶先生 161

### 习题四：
- 给定n个非负整数`a1,a2,...,an`，其中每个表示坐标(i,ia)处的点，使得线的两个端点位于x轴与y轴的(i,ia)和(i,0)。
- 找到两条线，它们与x轴一起形成一个可以含有最多水的容器。
- 求出最大容器的平面面积，您可能不会倾斜容器，n至少为2。

Input: `[1,8,6,2,5,4,8,3,7]`
Output: `49`
如下图所示：
![](/static/upload/bigpic/20181023/1540259599003727100_small.jpeg)
上面的垂直线由数组`[1,8,6,2,5,4,8,3,7]`表示。在这种情况下，容器可容纳水的最大平面面积（蓝色部分）为`49`。

### 解题思路：
我们必须最大化可以在垂直线之间形成的区域，最简单可用的办法肯定是计算每一对可能线的面积，最终得得到最大面积。

### 方法一：蛮力
```go
package main

import (
	"fmt"
	"math"
)

func maxArea1(height []int) int {
	maxarea := 0
	r := len(height)
	for i := 0; i < r; i++ {
		for j := i + 1; j < r; j++ {
			maxarea = int(math.Max(float64(maxarea), math.Min(float64(height[i]), float64(height[j])) * float64(j - i)))
		}
	}
	return maxarea
}

func main() {
	fmt.Println(maxArea1([]int{1,8,6,2,5,4,8,3,7}))
}
```
输出：
```go
49
```
时间复杂度：`n²`
很显然，既然提出了这种题目，肯定会有更优的办法来处理这种问题，可以自己先找一找直觉，还有什么方法可以降低时间复杂度呢？任何一种循环操作，如果找到中间的规律或要点，就有极大可能找到更优的办法，所以在这里总结一点经验，在学习阶段中，不要放过任何一个可以提升效率的机会，养成这样一个习惯，更不要任何问题都蛮力使用循环遍历，尽管循环遍历是最常用的，但也必须要让一些本身可能想不到的算法深刻引入脑中且同样成为自己处理问题的常用办法，毕竟效率是极重要的。

### 方法二：类似滑动窗口概念
个人觉得这个类似滑动窗口的概念，虽然不完全是。
首先可以找到2个规律：
1. 线与线之间形成的区域是受到较短线高度的限制。
2. 线的间隔越远，获得的区域越多。

因此我们可以指定两条最远的线为起点，向内逐一移动，移动时只移动其中较短的一条，因为移动较长的一条的话我们不会得到任何面积的增加，移动较短的一条才有可能增加面积。详细过程可查看下面的视频：
<video controls="" preload="none" poster="/static/upload/media/mp4/20181023/1540268914601055300.jpg"><source src="/static/upload/media/mp4/20181023/1540268914601055300.mp4" type="video/mp4"></video>

```go
package main

import (
	"fmt"
	"math"
)

func maxArea2(height []int) int {
	maxarea := 0
	l := 0
	r := len(height) - 1
	for l < r {
		maxarea = int(math.Max(float64(maxarea), math.Min(float64(height[l]), float64(height[r])) * float64(r - l)))
		if height[l] < height[r] {
			l++
		} else {
			r--
		}
	}
	return maxarea
}

func main() {
	fmt.Println(maxArea2([]int{1,8,6,2,5,4,8,3,7}))
}
```
时间复杂度：`n`

关键字词[算法]

分享到：

上一篇：leetcode基础算法学习之ReverseInt

下一篇：ansible学习记录-远程开启exe不能挂起UI界面

如需留言，请登录，没有账号？请注册

0 条评论 0 人参与