TrappingRainWater

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

필요한 자료구조 : 정수형 배열 2개 (left[ ], right[ ])

알고리즘 1. 왼쪽 벽(left)과 오른쪽 벽(right)을 구한다. - 정수형 배열 left[ ], right[ ] 생성. 2. left와 right 중 작은 값을 구한다. 둘 중 작은 값의 높이만큼 물이 차기 때문! - Math.min(l,r) 3. 자신의 벽 높이만큼 뺀다. => result += Math.min(left[i],right[i]) - height[i]

알고리즘을 java언어로 구현

class Solution {
    public int trap(int[] height) {
        int result = 0;
        //0.기저사례 제외!
        if(height==null || height.length <= 2)
            return result;
        //1.담을 그릇 생성
        int[] left = new int[height.length];
        int[] right = new int[height.length];
        
        
        //2. left와 right 배열에 데이터 넣기
        int max = height[0];
        left[0] = height[0];
        for(int i=1; i< height.length; i++) {
            if(max < height[i]) {
                max = height[i];
                left[i] = height[i];
            }
            else {
                left[i] = max;
            }
        }
        max = height[height.length-1];
        right[height.length-1] = height[height.length-1];
        for(int i=height.length-2; i >= 0; i--) {
            if(max < height[i]) {
                max = height[i];
                right[i] = height[i];
            }
            else {
                right[i] = max;
            }
        }
        //3. left와 right 둘중 작은 값을 선택!
        //자신의 높이만큼 뺀 값들을 더한 것이 result가 된다!
        for(int i=0;i < height.length;i++) {
            result += Math.min(left[i],right[i]) - height[i];
        }
        return result;
    }
}