LeetCode42.接雨水

 这道题呢可以按列来累加，就是先算第1列的水的高度然后再加上第2列水的高度……一直加到最后就是能加的水的高度，我想到了这里然后就想第i列的水其实就是第i-1列和i+1列中最小的高度减去第i列的高度，但是其实并不是，比如示例中的第5列，他的告诉是0左右两边是1，但水是2，然后看题解了。

第i列的水其实与第i-1列和i+1列的水并没有关系，而是和第i列左边所有柱子中最高的和第i列右边所有柱子中最高的有关

当第i列左右两边的最高柱子中较矮的比第i列要高，那么第i列能装的水就是较矮的高度-第i列的高度。如果左右两边最高的柱子都比第i列的柱子矮的话，那么第i列能装的水就是0。所以算出每一列能装的水然后全部加起来就是能接到的雨水，以下的代码：

class Solution {public int trap(int[] height) {int n = height.length;int ans = 0;for(int i =1;i<n-1;i++){int leftMaxHeight =0;for(int j =i-1;j>=0;j--){if(height[j] > leftMaxHeight)leftMaxHeight=height[j];}int rightMaxHeight =0;for(int k =i+1;k<n;k++){if(height[k] > rightMaxHeight)rightMaxHeight=height[k];}int min = Math.min(rightMaxHeight, leftMaxHeight);ans+= min > height[i] ? min-height[i] : 0;}return ans;}
}

这个算法每次都要找出某一列左边的最高的柱子和右边的最高柱子，就多了一层循环，算法还可以优化，创建一个left_max数组和right_max数组，left_max[i]表示第i列左边的最高的柱子，right_max[i]同理。用动态规划的方法来填充这两个数组。

left_max[i] = Math,max(left_max[i-1] ,height[i-1]);就是说第i列左边最高的柱子是第i-1列左边的最高柱子第i-1列的高度的最大值,right_max[i]同理。以下是代码：

public int trap(int[] height) {int sum = 0;int[] max_left = new int[height.length];int[] max_right = new int[height.length];for (int i = 1; i < height.length - 1; i++) {max_left[i] = Math.max(max_left[i - 1], height[i - 1]);}for (int i = height.length - 2; i >= 0; i--) {max_right[i] = Math.max(max_right[i + 1], height[i + 1]);}for (int i = 1; i < height.length - 1; i++) {int min = Math.min(max_left[i], max_right[i]);if (min > height[i]) {sum = sum + (min - height[i]);}}return sum;
}