题目描述

原题链接

个人解法

Javascript

Java

class Solution {
    public int trap(int[] height) {
        int len = height.length, sum = 0, left = 0, right = 0,flag=0;
        for (int i = 1; i <len-1;i++){
            for (int j=i-1;j>=0;j--){
                left=Math.max(left,height[j]);
            }
            for (int j=i+1;j<len;j++){
                right=Math.max(right,height[j]);
            }
            left=Math.min(right,left);
            if (left>height[i]){
                sum+=(left-height[i]);
            }
            left=0;
            right=0;
        }
        return sum;
    }
}

其他解法

Java

动态规划

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;
}

Javascript