42. Trapping Rain Water

        // let w(i) represent the amount of water trapped at position i
        // h(left) represent the highest height on left of i, 
        // h(right) represent the highest height on the right of i,
        // w(i) = min(h(left), h(right)) - h(i);

DP:

class Solution {
    public int trap(int[] height) {
        int[] l = new int[height.length];
        int[] r = new int[height.length];
        int leftMax = 0;
        for(int i = 0; i<height.length; i++){
            leftMax = i == 0 ?  height[i] : Math.max(l[i-1], height[i]);
            l[i] = leftMax;
        }
        
        int rightMax = 0;
        for (int j= height.length-1; j>=0; j--){
            rightMax = j == height.length-1 ? height[j] : Math.max(height[j], r[j+1]);
            r[j] = rightMax;
        }
        
        int sum = 0;
        for (int k = 0; k<height.length; k++){
            sum += Math.min(l[k], r[k])-height[k];
        }
        return sum;
    }
}

Two pointers:

class Solution {
    public int trap(int[] height) {
        int l = 0;
        int r = height.length-1;
        
        //represent the maxium height in the range [0, l];
        int maxL = 0;
        //represent the maxium height in the range [r, height.length-1];
        int maxR = 0;
        int sum = 0;
        while(l<r){
            maxL = Math.max(maxL, height[l]);
            maxR = Math.max(maxR, height[r]);
            if (maxL<=maxR){
                sum+=maxL-height[l];
                l++;
            }else{
                sum += maxR-height[r];
                r--;
            }
        }
        return sum;
    }
}