一、简介

给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度视为0)

案例

输入：
[3,1,2,5,2,4]  
返回值：
5 
说明：
数组 [3,1,2,5,2,4] 表示柱子高度图，在这种情况下，可以接 5个单位的雨水，蓝色的为雨水 ，如题面图。

二、实现

func maxWater(arr []int)  int64{
	if len(arr) <=2 {
		return 0
	}

	// 确定左边节点
	leftIndex := 0
	for i:=1; i< len(arr); i++ {
		if arr[i] < arr[leftIndex] {
			break
		}

		leftIndex ++
	}

	if leftIndex == len(arr) -1 {
		return 0
	}

	// 确定 中间最低点
	midIndex := leftIndex +1
	for i:= leftIndex+2; i < len(arr); i++ {
		if arr[i] > arr[midIndex] {
			break
		}

		midIndex ++
	}

	if midIndex == len(arr) -1 {
		return 0
	}


	// 确定 右侧的最高点
	rightIndex := midIndex +1
	for i:= rightIndex+1; i< len(arr); i++ {
		if arr[rightIndex] > arr[leftIndex] {
			break
		}

		if arr[i] > arr[rightIndex] {
			rightIndex = i
		}
	}

	// 计算从leftIndex ~ rightIndex 直接可存储的水量
	maxVal := 0
    minNode := arr[leftIndex]
	if arr[leftIndex] < arr[rightIndex] {
		minNode = arr[leftIndex]
	} else{
	    minNode = arr[rightIndex]
	}
    
	// 去掉中间的节点
	for i:= leftIndex+1; i< rightIndex; i++ {
		maxVal += minNode - arr[i]
	}

	if rightIndex == len(arr) -1 {
		return int64(maxVal)
	}

	return int64(maxVal) + maxWater(arr[rightIndex:])
}

题目来源：牛客