42. Trapping Rain Water - Streak 12

가장 간단한 풀이 - O(n*h[i])
양 옆에 이것보다 큰 숫자가 있었던 적이 있으면 물이 담길 수 있게 된다.
물은 양 방향 중 작은 숫자 - 현재 높이만큼 담길 수 있다.

 

즉 우리에게 필요한 것은 양 방향의 가장 큰 숫자이다.
이는 배열 양쪽 방향으로 스윕하는 전처리를 수행하면 O(1)만에 구할 수 있다.

 

시간복잡도: O(n)

너무 쉬워서 유사 문제가 있나 봤더니
백준 14719 빗물 - Gold V 문제가 있었다.

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] prefix = new int[n+1];
        int[] suffix = new int[n+1];

        int left = 0;
        for(int i = 0; i<n; i++){
            prefix[i] = left;
            left = Math.max(left, height[i]);
        }

        int right = 0;
        for (int i = n-1; i>=0; i--){
            suffix[i] = right;
            right = Math.max(right, height[i]);
        }

        int ret = 0;
        for(int i = 0; i<n; i++){
            int can = Math.min(prefix[i], suffix[i]) - height[i];
            ret += Math.max(0, can);
        }
        return ret;
    }
}