[Leetcode] 42. Trapping Rain Water - Java

 

 

문제 LINK

 

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

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.

 

-> 너비가 1인 막대기로 구성된 elevation map에서 , 비가 내린 후에 얼마나 많은 물이 갇히는지 계산

 

 

 

---

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: 
The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. 
In this case, 6 units of rain water (blue section) are being trapped.

 

 

 

 

---

문제 풀이

 

Stack 을 통한 접근 

 

Stack에는 각 막대기의 높이에 해당하는 인덱스를 저장
반복문을 돌면서, 스택이 비어있지 않고 현재 막대기의 높이가 이전 막대기의 높이보다 큰 경우 찾기

 

이때, 현재 막대기의 높이와 이전 막대기의 높이 사이에 물이 담길 수 있음

 * 이전 막대의 높이를 top 저장, 그 다음 stack을 확인했을 때 빈 값인 경우는 왼쪽 막대기가 존재하지 않는 경우라 제외.

 

스택에서 이전 막대기의 인덱스를 꺼내어 현재 막대기와 이전 막대기 사이에 담길 수 있는 물의 양을 계산

 * dist(간격) : 현재위치 - 스택의 Indx - 1

 * bounded_height(둘러쌓인 높이)  : 두 막대기 사이의 높이 중 최솟값을 뽑아내고 이를 현재 저장한 top(물이 들어갈 곳의 높이)을 빼줌.

 * ans = dist x bounded_height 를 더해나감.

 

실행 예시

1. 첫번째 While 문에 의해 stack에   0 저장 
2. !stack.empty() && height[current] > height[stack.peek()] 에 해당되어, top 에 0이 저장되고 pop 되면서 stack이 empty  break -> stack 1 저장
3. stack 에 2 저장
4. height[current] > height[stack.peek()] , 두번째 While 문  -> dist (간격 구함, 1) -> height 높이 1 -> ans 에 추가 - > 두번째 while 문 실행 ->  pop 되면서 stack empty -> stack 3 저장  
5. stack 4 저장
6. stack 5 저장

class Solution {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>(); 
        int ans =0;
        int current = 0;

        while(current < height.length){

            while(!stack.empty() && height[current] > height[stack.peek()]){
                int top = stack.peek();
                stack.pop();
                if(stack.empty()){
                    break;
                }
                int dist = current - stack.peek() - 1;
                int bounded_height = Math.min(height[current], height[stack.peek()])- height[top];
                //System.out.println("bounded_height "+ bounded_height+ " dist "+ dist);
                ans += dist * bounded_height;
            }
            stack.push(current++);

        }

        return ans;

    }
}