[array] trapping rain water

✅ Problem

https://leetcode.com/problems/trapping-rain-water/description/

 

✅ Approach & Solution

조건

• 물이 고이려면 양 쪽이 막혀있어야 한다.
• 양 쪽 높이 중 더 낮은 높이까지만 물이 고일 수 있다.

 

방식1) 투 포인터 사용

• 배열이 주어졌을 때 O(N) 시간복잡도로 구현하려면 투 포인터 방식 사용
  • 배열의 양 끝에서 시작, left < right 동안 반복

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

        // 투 포인터가 서로 겹칠 때까지 반복
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);

            // 더 높은 쪽을 향해 투 포인터 이동
            if (leftMax <= rightMax) {
                // 왼쪽 막대 최대 높이와의 차이를 더하고 왼쪽 포인터 이동
                volume += (leftMax - height[left]);
                left += 1;
            } else {
                // 오른쪽 막대 최대 높이와의 차이를 더하고 오른쪽 포인터 이동
                volume += (rightMax - height[right]);
                right -= 1;
            }
        }
        return volume;
    }
}

 

방식2) 스택 사용

class Solution {
    public int trap(int[] height) {
        Deque<Integer> stack = new ArrayDeque<>();
        int volume = 0;

        for (int i = 0; i < height.length; i++) {
            // 변곡점을 만나는 경우
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                // 스택에서 꺼냄
                Integer top = stack.pop();

                if (stack.isEmpty()) {
                    break;
                }

                // 스택의 마지막 위치까지를 거리로 계산
                int distance = i - stack.peek() - 1;
                // 현재 높이 또는 스택의 마지막 위치 높이 중 낮은 값에 방금 꺼낸 높이의 차이를 물 높이로 지정
                int waters = Math.min(height[i], height[stack.peek()]) - height[top];

                // 물이 쌓이는 양은 거리와 물 높이의 곱
                volume += distance * waters;
            }

            // 진행하면서 현재 위치를 스택에 삽입
            stack.push(i);
        }
        
        return volume;
    }
}