문제

Trapping Rain Water - LeetCode

Code

class Solution {
    public int trap(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int leftMax = height[left];
        int rightMax = height[right];
        int volume = 0;

        while (left < right){
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);

            if (leftMax <= rightMax){
                volume += leftMax - height[left];
                left ++;
            } else {
                volume += rightMax - height[right];
                right --;
            }
        }

        return volume;
    }
}

1. 투 포인터를 이용하여 양 끝에서 가장 높은 블럭을 향해 나아가는 방식이다.
   1. height를 한번만 탐색하므로 O(n)으로 풀이가 가능하다.

파이썬 알고리즘 인터뷰를 풀면서 풀었던 문제였지만 여전히 어렵다.