接雨水

题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例:

rainwatertrap.png

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

解题思路

1. 计算每个柱子可以承载的雨量，然后相加
2. 每个柱子的雨量= 左边和右边最高柱子高度的min值-自身柱子高度。
3. 双循环分别求解左右最符合条件的柱子
   时间复杂度O(n^2)，因为每个柱子都需要双向遍历所有柱子，n*n。

代码

class Solution {
    public int trap(int[] height) {
        int res = 0;
        for (int i = 0; i < height.length; i++){
            int num = getNum(height,i);
            res += num;
        }
        return res;
    }
    public int getNum (int[] height,int index){
        int value;
        int leftValue = height[index];
        for (int i = index; i>=0;i--){
            leftValue = height[i] > leftValue ? height[i]:leftValue;
        }
        int rightValue = height[index];
        for (int i = index; i< height.length;i++){
            rightValue = height[i] > rightValue ? height[i]:rightValue;
        }
        value = leftValue < rightValue?leftValue:rightValue;
        if (value > height[index]){
            return value - height[index];
        }else
        {
            return 0;
        }
    }
}