[leetcode 42] Trapping Rain Water

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.

 

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.

Example 2:

Input: height = [4,2,0,3,2,5] Output: 9

 

Constraints:

• n == height.length
• 0 <= n <= 3 * 104
• 0 <= height[i] <= 105

문제 풀이:

nhn 1차 pretest에서 나왔는데 못푼 문제이다.

 

방법은 3가지: brute force/stack/2 pointer

 

1 brute force 이용

 

maxHeight 배열 만들기

1. 왼쪽부터 오른쪽으로 막대기의 최대 길이를 업데이트 하여 저장한다. max(maxLen, height[i])

2. 다시 오른쪽부터 왼쪽으로 막대기의 최대길이를 업데이트하여 저장하되 이 때는 min(기존에 저장된 최대 길이, 현재 최대 길이)를 저장한다.

 

3. 이제 maxHeight 배열에서 본래 빌딩 높이 배열을 빼준다. 이 때 차이값을 정답에 더해주면 된다.

파란색은 왼쪽에서부터 최대 길이를 체크한 것이고 빨간 색은 오른쪽에서부터 최대 길이를 체크한 것이다.

 

1,2를 마치고 나면 maxHeight에 저장된 값은 0 1 1 2 2 2 2 3 2 2 2 1 이 된다.

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> maxArr(n,0);
        int maxHeight = 0;
        for(int i=0; i<n; i++){
            maxHeight = max(maxHeight, height[i]);
            maxArr[i] = maxHeight;
        }
        maxHeight = 0;
        for(int i=n-1; i>-1; i--){
            maxHeight = max(maxHeight, height[i]);
            
            if(maxHeight < maxArr[i]){
             maxArr[i] = maxHeight;   
            }
        }
        
        int ans=0;
        for(int i=0; i<n; i++){
            ans+= maxArr[i] - height[i];
        }
        return ans;
    }
};

 

2 stack 사용

빗물이 고이는 시점은 막대기 길이가 긴거 -> 작은거 순서로 나오다가 갑자기 긴 막대기가 나왔을 때이다. (작은거 -> 긴 거 면 빗물 안고임 empty에서 break하는 이유)

따라서 스택이 비어있거나 이전 막대기가 현재 막대기보다 길다면 계속 push한다.

이전 막대기보다 긴 막대기가 등장했다면 그 때부터 빗물의 양을 측정한다.

 

 

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int idx = 0, ans=0;
        
        stack<int> st;
       
        while(idx<n){
            
                while(!st.empty() && height[st.top()] < height[idx]){
                    int top = st.top();
                    st.pop();
                    
                    if(st.empty()){
                        break;
                    }
                    
                    int width = idx - st.top() -1;
                    int tmp_height = min(height[idx], height[st.top()]) - height[top];
                    
                    ans += width * tmp_height;
                }
                st.push(idx++);

            
        }
        return ans;
    }
};

 

 

3 투포인터 사용

 

leftMax는 left의 왼쪽에, rightMax는 right의 오른쪽에 있을 것이다. 

leftMax< rightMax의 의미는 오른쪽에 현재보다 긴 막대기가 존재할 것이라는 의미이므로 짧은 막대기를 기준으로 물의 양을 계산한다.

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int left = 0, right = n-1, ans=0;
        
        int leftMax = 0, rightMax=0;
        
        while(left<right){
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);
            
            if(leftMax < rightMax){
                ans += max(0, leftMax - height[left++]);
            }else {
                ans += max(0, rightMax - height[right--]);
            }
        }
        
        return ans;
    }
};