7.接雨水

题目概述：给定一些柱子的高度，问这些柱子能够接到多少雨水
解题思路：将每个位置都想象有一个木桶，接到雨水的量=木桶体积-柱子体积。木桶的高度由前后缀数组中的较小者决定
时间复杂度：\(O(n)\)
代码：

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int pre[] = new int[n];
        int suf[] = new int[n];

        pre[0] = height[0];
        suf[n - 1] = height[n - 1];
        for(int i = 1; i < n; i ++)pre[i] = Math.max(height[i],pre[i - 1]);
        for(int i = n - 2; i >= 0; i --)suf[i] = Math.max(height[i],suf[i + 1]);

        int rainCount = 0;
        for(int i = 0; i < n; i ++)rainCount += Math.min(pre[i],suf[i]) - height[i];

        return rainCount;

    }
}