[leetcode] 42. Trapping Rain Water

 

 

[leetcode] 42. Trapping Rain Water

 

 

Trapping Rain Water - LeetCode

 

 

[문제]

 

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.

 

 

[입출력]

 

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

 

 

[풀이]

 

작은 블럭 기준으로 현재 자신의 높이를 빼서 빗물을 담을 수 있다.

왼쪽과 오른쪽의 최대 높이를 각각 배열로 만들어 담고 둘 중 작은 블럭 기준으로 자신의 높이를 빼면 된다.

max와 min을 잘 활용하여 해결할 수 있는 문제이다.

 

 

[코드]

 

class Solution {
    public int trap(int[] height) {
        int result = 0;
		int len = height.length;
		
		//1.leftMax
		int[] left = new int[len];
		int max = height[0];
		for (int i = 0; i < len; i++) {
			max = Math.max(max, height[i]);
			left[i] = max;
		}
		
		//2.rightMax
		int[] right = new int[len];
		max = height[len-1];
		for (int i = len-1; i >= 0; i--) {
			max = Math.max(max, height[i]);
			right[i] = max;
		}
		
		//3.계산
		for (int i = 0; i < len; i++) {
			result += Math.min(left[i], right[i]) - height[i];
		}
		
		
		return result;
    }
}