积蓄雨水问题

  最近对算法产生了兴趣，由于读书的时候并没有怎么参与编程比赛，不免觉得有点缺憾，但是做为一个程序员，生活本来就是一场修行，需要不断提高自己的专业能力，这种缺憾还是不要留的好。leecode是个不错的平台，它对找工作比较有用，但是对于满足这种写算法题的需求也很是适合。

  下面是一道计算积累多少雨水的题目；输入一个数组，输出一个值；从模型上看，问题简直简单明了，用程序来解决这个问题，不免让人跃跃欲试。

rainwatertrap

  输入数组为[1,0,2,1,0,1,3,2,1,2,1];输入代表的是上图中的黑色方块；

  输出为蓝色方块的数目为6；

  第一眼看到这个问题，很直观的思路就是从左到右进行遍历，记录数字上升的趋势。当遇到一个下降的值的时候，表示找到一个凹点，进行结算；于是写下代码：

    func trapRain(_ height:[Int]) -> Int {
        if(height.count < 2) {
            return 0
        }
        
        var tempHeight = height
        tempHeight.append(0)
        
        var rainWeight = 0
        var index = 1
        var isAsendTrend = true
        var subValue:Array<Int> = Array.init()
        subValue.append(tempHeight[0])
        /*
            几种需要进行结算的情况
            1、上升趋势转变成下降趋势（相等视为不改变趋势）
            2、上升趋势到最后一个元素
            3、在每一个凹点的第一个和最后一个元素中取一个小值做为平均高度
         eg:[0,1,0,2,1,0,1,3,2,1,2,1]
         [0,1,0,1] => [0,1,0,1,0]
         */
        while index < tempHeight.count {
            if tempHeight[index] < tempHeight[index-1] {
                if isAsendTrend {
                    rainWeight = rainWeight + calculateSubValue(subValue, min(subValue[0], tempHeight[index-1]))
                    subValue.removeAll()
                    subValue.append(tempHeight[index-1])
                    subValue.append(tempHeight[index])
                }
                else {
                    subValue.append(tempHeight[index])
                }
                isAsendTrend = false
            }
            else {
                isAsendTrend = true
                subValue.append(tempHeight[index])
            }
            
            index = index + 1
        }
        return rainWeight
    }

用于结算每一个凹点的函数:

func calculateSubValue(_ subvalues:Array<Int>, _ height:Int) -> Int {
        var result = 0
        var index = 0
        while index < subvalues.count {
            if height > subvalues[index] {
                result = result + height - subvalues[index]
            }
            index = index + 1
        }
        return result
    }

  输入测试用例[0,1,0,1],输出1，正确
  再输入[0,1,0,2,1,0,1,3,2,1,2,1],输出6，正确
  感觉信心满满，以为找到来正确的解法，一提交，直接显示wrong answer！！感觉被当头一棒;
  研究一下导致出错的用例[3,1,2,1,2,3],
  这种用上面的方法，第一次2到1的时候下降，以为找到了一个凹点[3,1,2]，实际上这个凹点只是一个局部凹点，它包含在一个更大的凹点之内。对于这样一种情况，上述算法并不能cover到！看样子要找到一种能够计算更大范围凹点的方式。
  仔细想想，其实数值由上升到下降只能说找到了一个局部凹点，如果找到一个新值比之前凹点起始值还大的话，那就必然找到了一个不属于任何凹点的独立凹点。另外，可以从两头开始向中间搜索，每次递减较小的索引。写出代码：

func trapRainV2(_ height:[Int]) -> Int {
        if(height.count < 2) {
            return 0
        }
        
        var rainWeight = 0
        
        var leftIndex = 0
        var rightIndex = height.count - 1
        
        var subValueLeft:Array<Int> = Array.init()
        var subValueRight:Array<Int> = Array.init()
        
        var rightStart = height[rightIndex]
        var leftStart = height[leftIndex]
        
        var isChangeLeft = true
        
        subValueLeft.append(leftStart)
        subValueRight.append(rightStart)
        
        while(leftIndex < rightIndex) {
            
            //左边找到第一个比起始位置大的值，结算
            if height[leftIndex] >= leftStart && subValueLeft.count > 0 && isChangeLeft {
                rainWeight = rainWeight + calculateSubValue(subValueLeft, min(leftStart, height[leftIndex]))
                subValueLeft.removeAll()
                leftStart = height[leftIndex]
                subValueLeft.append(height[leftIndex])
            }
            
            //右边找到第一个比起始位置大的值，结算
            if height[rightIndex] >= rightStart && subValueRight.count > 0 && !isChangeLeft {
                rainWeight = rainWeight + calculateSubValue(subValueRight, min(rightStart, height[rightIndex]))
                subValueRight.removeAll()
                rightStart = height[rightIndex]
                subValueRight.append(height[rightIndex])
            }
            
            //更新索引，每次较小的值向中间聚拢一个单位
            if(height[leftIndex] < height[rightIndex]) {
                //储存凹点的值
                if height[leftIndex] < leftStart {
                    subValueLeft.append(height[leftIndex])
                }
                leftIndex = leftIndex + 1
                isChangeLeft = true
            }
            else {
                if height[rightIndex] < rightStart {
                    subValueRight.append(height[rightIndex])
                }
                rightIndex = rightIndex - 1
                isChangeLeft = false
            }
        }
        
        if subValueRight.count>1 || subValueLeft.count > 1 {
            let lowHeight = min(leftStart, rightStart)
            rainWeight = rainWeight + calculateSubValue(subValueLeft, lowHeight)
            rainWeight = rainWeight + calculateSubValue(subValueRight, lowHeight)
        }
        
        return rainWeight
    }

其实思路倒是很快就有了，但是要形成上述可以通过的代码，过程还是有点纠结的。其中一些比较的边际值调整了好几次，例如，count该大于1还是0？这种地方比较细节，但是却会影响到最终的结果。整个过程并不顺利，想想那些看到题目一遍就可以把代码写对的人，实在差距有些大，这方面还要好好磨砺啊！