LeetCode 接雨水

[TOC]

#### 题目描述
此题选自 [LeetCode 接雨水](https://leetcode-cn.com/problems/trapping-rain-water/  "领扣")

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。**感谢 Marcos 贡献此图。**
![](http://image.gwalker.cn/article_2018-11-292785bff5969d577c51337.png)
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）

> 示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

#### 算法思路
分解为每一层，分别进行统计。先看最底层能接多少雨水，然后再依次第二层，第三层......最高层。

#### 时间复杂度分析
O(m\*n) m为数组的长度，n为数组中的最大值.如果n很大，**这个算法很低效**。

> 下面给出了不同语言的实现代码。此算法遍历每一层，不是最优算法。值得一提的是，不同的编程语言实现，采用相同的算法，**只有go语言在[领扣](https://leetcode-cn.com/problems/trapping-rain-water/  "领扣")上能提交通过。其它语言的实现代码(包含C语言),都会超时间，提交失败。**

#### 不同语言的实现方法

##### golang版
```golang
func trap(height []int) int {
	sum := 0
	length := len(height)
	i := 0
	flag := true
	for{
		prefixFlag := 0
		temp := 0
		flag = true
		for j := 0; j < length; j++ {
			if height[j] >= i {
				prefixFlag = 1
				sum += temp
				temp = 0
				flag = false
			} else {
				if prefixFlag == 1 {
					temp ++
				}
			}
		}
		i++
		if flag {
			break
		}
	}
	return sum
}
```

#####  c语言版

```c
int trap(int* height, int heightSize) {
    int sum = 0;
    int i = 0;
    bool flag = true;
    int prefixFlag = 0 ;
    int temp = 0;
    while(1){
        prefixFlag = 0 ;
        temp = 0;
        flag = true;
        for (int j = 0; j < heightSize; j++) {
            if (height[j] >= i) {
                prefixFlag = 1;
                sum += temp;
                temp = 0;
                flag = false;
            } else {
                if (prefixFlag == 1) {
                    temp ++;
                }
            }
        }
        i++;
		if (flag) {
			break;
		}
    }
    return sum;
}
```

##### java版

```java版
class Solution {
    public int trap(int[] height) {
        boolean prefixFlag = false;
        int temp = 0;
        int sum = 0;
        int length = height.length;
        int i=1;
        boolean flag = false;
        while(true){
            prefixFlag  = false;
            temp = 0;
            flag = false;
            for(int j=0;j<length;j++){
                if(height[j]>=i){
                    flag = true;
                    prefixFlag = true;
                    sum += temp;
                    temp = 0;
                }else{
                    if(prefixFlag){
                        temp++;
                    }
                }
            }
            if(!flag){
                break;
            }
            i++;
        }
        return  sum;
    }
}
```

##### javascript版
```javascript
var trap = function(height) {
    var sum = 0;
    var i = 0;
    var heightSize = height.length
    var flag = true;
    var prefixFlag = 0 ;
    var temp = 0;
    while(1){
        prefixFlag = 0 ;
        temp = 0;
        flag = true;
        for (var j = 0; j < heightSize; j++) {
            if (height[j] >= i) {
                prefixFlag = 1;
                sum += temp;
                temp = 0;
                flag = false;
            } else {
                if (prefixFlag == 1) {
                    temp ++;
                }
            }
        }
        i++;
		if (flag) {
			break;
		}
    }
    return sum;
};
```

##### python3版
```python
class Solution:
    def trap(self, height):
        sum = 0;
        i = 0;
        flag = True;
        heightSize = len(height);
        prefixFlag = 0;
        temp = 0;
        i = 1;
        while 1:
            prefixFlag = 0 ;
            temp = 0;
            flag = True;
            for value in height:
                if value >= i:
                    prefixFlag = 1;
                    sum += temp;
                    temp = 0;
                    flag = False;
                else:
                    if prefixFlag == 1:
                        temp += 1;
            i += 1;
            if flag :
                break;
        return sum
```

##### swift版
```swift
class Solution {
    func trap(_ height: [Int]) -> Int {
        var sum = 0;
        var i = 0;
        var flag = true;
        var prefixFlag = false;
        var temp = 0;
        var length = height.count;
        while true {    
            prefixFlag  = false;
            temp = 0;
            flag = false;
            for val in height{
                if val >= i {
                    flag = true;
                    prefixFlag = true;
                    sum += temp;
                    temp = 0;
                }else{
                    if prefixFlag {
                        temp += 1;
                    }
                }
            }
            if !flag {
                break;
            }
            i += 1;
        }
        return sum
    }
}
```

##### ruby版
```ruby
# @param {Integer[]} height
# @return {Integer}
def trap(height)
    $sum = 0
    $i = 0
    $flag = true
    $prefixFlag = false
    $temp = 0
    $length = height.size
    
    while 1 do
        $prefixFlag  = false
        $temp = 0
        $flag = false
        for a in height do  
            if a >= $i 
                $flag = true
                $prefixFlag = true
                $sum += $temp
                $temp = 0
            else
                if $prefixFlag
                    $temp += 1
                end    
            end
        end
        
        if !$flag 
            break    
        end
        $i += 1
    end
    
    return $sum
end
```

#### golang实现 代码调优过程
##### 第一版
```golang
func trap(height []int) int {
	sum := 0
	max := 0

// 找最大值
	for _,v := range height {
		if v > max {
			max = v
		}
	}

// 构建二维切片 max行,len(height)列
	layers := make([][]int, max)
	for i := 0; i < max; i++ {
		layers[i] = make([]int, len(height))
	}

// 分解每一层，存入到二维切片
	for i := 0 ;i < max ; i++ {
		for k,v := range height {
			if v - i > 0 {
				layers[i][k] = 1
			} else {
				layers[i][k] = 0
			}
		}
	}

//fmt.Println(layers)

// 将第二维的切片首尾连续为0都置为1(方便逻辑判断)
	for i,layer := range layers {
		// 首连续0处理
		for head,_ := range layer {
			if layers[i][head] == 0 {
				layers[i][head] = 1
			}else{
				break
			}
		}

// 尾连续0处理
		for tail := len(height) -1 ; tail > 0; tail-- {
			if layers[i][tail] == 0 {
				layers[i][tail] = 1
			}else{
				break
			}
		}

// 统计0的数量
		for head,_ := range layer {
			if layers[i][head] == 0 {
				sum ++
			}
		}
	}

return sum

}
```
##### 第二版
> 优化 去掉二维切片的申请。降低内存占用空间

```golang
func trap(height []int) int {
	sum := 0
	max := 0

// 找最大值
	for _,v := range height {
		if v > max {
			max = v
		}
	}

// 分解每一层
	layer := make([]int, len(height))
	for i := 0 ;i < max ; i++ {
        
		for k,v := range height {
			if v - i > 0 {
				layer[k] = 1
			} else {
				layer[k] = 0
			}
		}

// 首连续0处理
		for head,_ := range layer {
			if layer[head] == 0 {
				layer[head] = 1
			}else{
				break
			}
		}

// 尾连续0处理
		for tail := len(height) -1 ; tail > 0; tail-- {
			if layer[tail] == 0 {
				layer[tail] = 1
			}else{
				break
			}
		}

// 统计0的数量
		for head,_ := range layer {
			if layer[head] == 0 {
				sum ++
			}
		}
	}
	return sum
}

```

##### 第三版

> 再次优化不用取最大值，不用额外再次处理首尾的连续0

```golang
package main

import "fmt"

func trap(height []int) int {
	sum := 0
	length := len(height)
	i := 0
	flag := true
	for{
		prefixFlag := 0
		temp := 0
		flag = true
		for j := 0; j < length; j++ {
			if height[j] >= i {
				prefixFlag = 1
				sum += temp
				temp = 0
				flag = false
			} else {
				if prefixFlag == 1 {
					temp ++
				}
			}
		}
		i++
		if flag {
			break
		}
	}
	return sum
}
```