class Solution {
    public int trap(int[] height) {

        int sum = 0;
        for(int i=1; i<=height.length-2; i++){
            int hei_min = find(height, i);
            if(hei_min > height[i]){
                sum += (hei_min-height[i]);
            }
        }
        return sum;
    }

	//找到左边最高柱子 和 右边最高柱子 中较矮的那一个
    int find(int []height, int i){
        int left = height[0];
        int right = height[i+1];
        for(int k=0; k<i; k++){
            left = Math.max(left, height[k]);
        }
        for(int k=i+1; k<height.length; k++){
            right = Math.max(right, height[k]);
        }

        return Math.min(left, right);
    }
}

时间复杂度： O(N^2)

空间复杂度： O(1)

2、动态规划

暴力解法的时间复杂度显然太高了，我们可以使用动态规划降低一下时间复杂度。

使用动态规划，通过一遍遍历，将每个位置的左右最高保存下来。这样只用一重循环即可。

class Solution {
    public int trap(int[] height) {

        int len = height.length;
        if(len == 0){
            return 0;
        }

        int []left_max = new int[len];
        int []right_max = new int[len];
        left_max[0] = height[0];
        right_max[len-1] = height[len-1];

        left_max[0] = height[0];
        right_max[0] = height[0];
        //找出每个位置的左边最高的高度
        for(int i=1; i<len; i++){
            left_max[i] = Math.max(left_max[i-1], height[i]);
        }
        //找出每个位置的右边最高的高度
        for(int i=len-2; i>=0; i--){
            right_max[i] = Math.max(right_max[i+1], height[i]);
        }

        int res = 0;
        for(int i=0; i<len; i++){
            int hei = Math.min(left_max[i], right_max[i]);
            if(hei > height[i]){
                res += (hei-height[i]);
            }
        }
        return res;
    }
}

时间复杂度： O(N)

空间复杂度： O(N)

3、双指针

那能不能把空间优化一下呢？

其实仔细观察不难发现，当某个位置的一侧有更高的柱子时，这个位置的蓄水量仅由另一侧决定

public int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int ans = 0;
    int left_max = 0, right_max = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= left_max) {
                left_max = height[left];
            } else {
                ans += (left_max - height[left]);
            }
            ++left;
        } else {
            if (height[right] >= right_max) {
                right_max = height[right];
            } else {
                ans += (right_max - height[right]);
            }
            --right;
        }
    }
    return ans;
}

时间复杂度： O(N)

空间复杂度： O(1)

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/125014.html