Loop Solution - Trapping Rain Water

The idea is to create one/two depends on how to program it… arrays to record left to right max of each node, and then update it from right to left. After updating, use each minus A corresponding element, and sum the results return.


public class Solution {
    public int trap(int[] A) {
        if(A == null || A.length < 2){
            return 0;
        }
        int[] maxL = new int[A.length];
        int[] maxR = new int[A.length];
        int max = A[0];
        maxL[0] = 0;
        for(int i = 1; i < A.length - 1; i++){
            maxL[i] = max;
            if(max < A[i]){
                max = A[i];
            }
        }
       
        int sum = 0;
        int cur = 0;
        max = A[A.length - 1];
        for(int i = A.length - 2; i > 0; i--){
            maxR[i] = max;
            cur = Math.min(maxR[i], maxL[i]) - A[i];
            if(cur > 0){
                sum += cur;
            }
            if(max < A[i]){
                max = A[i];
            }
        }
        return sum;
    }
}