[LeetCode] Trapping Rain Water (Java)

leetcode.com/problems/trapping-rain-water/

Trapping Rain Water - LeetCode

문제 : 각 막대의 너비가 1 인 고도를 나타내는 음이 아닌 정수 n 개가 주어지면 비가 내린 후 가둘 수있는 물의 양을 계산합니다.

 

Example:Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6

 

접근 아이디어 :

1. 한 방향으로만 가둘 수 있는 물의 양을 고려하면 최고 높이를 기준으로 하강하는 부분에서 계산 방법이 달라진다.

2. 양 쪽에서 가둘 수 있는 물의 양을 구한다. (그래서 최고 높이를 기준으로 삼는다)

3. 최고 높이는 중복이 될 수 있다. (가장 왼쪽이든 가운데든 가장 오른쪽이든 기준은 마음대로 잡아도 상관없다) 

 

class Solution {   
    public int trap(int[] height) {
        if(height.length == 0) return 0;
        int trap = 0;
        int top = height[0], index = 0;
        for(int i=0; i<height.length; i++) {
            if(top <= height[i]) {
                index = i;
                top = height[i];
            }
        }
        int left = height[0];
        for(int i=0; i<index; i++) {
            if(height[i] > left) left = height[i];
            else if(height[i] < left) trap += (left - height[i]);
        }
        int right = height[height.length - 1];
        for(int i=height.length-1; i>index; i--) {
            if(height[i] > right) right = height[i];
            else if(height[i] < right) trap += (right - height[i]);
        }
        return trap;
    }
}