Leetcode - 42. Trapping Rain Water [H]

문제

높이값이 나열된 배열이 있다. 비가와서 물이 고일때, 최대 고인물(?)의 양은 얼마인가?

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.

해결 - Monotonic Stack O(n) / O(n)

기본적으로 descreasing monotonic stack을 사용하여 풀 수 있다. stack에 top 높이가 작은 값만 push할 수 있다. 만약 현재 높이가 stack의 top보다 크다면, pop을 한다. stack에는 index를 push한다.

    ⬛️ 
⬛️  ⬛️
⬛️⬛️⬛️
1 0 2 <- 높이값

그런데 단순히 pop이 아니라, 조금 더 복잡한 계산을 해야한다. pop을 하는 경우의 형태는 위와 같이 U 구덩이모양의 형태밖에 없다. 스택의 top위치는 반드시 물이 고이는 위치다.(위 그림에서 높이가 0인지점) top이전 값은 top보다 무조건 높이가 높고(deceasing monotonic stack규칙에따라), 현재값도 top보다 무조건 높이가 높기 때문이다. 이 형태에서 고이는 물의 높이는 1과 2중 작은값인 1이 될것이다.

      ⬛️   
⬛️    ⬛️  
⬛️⬛️  ⬛️
⬛️⬛️⬛️⬛️
2 1 0 3 <- 높이값.

위와 같이 높이 h[]배열 값이 {2,1,0,3} 으로 주어진다고 하자. 아래의 동작을 수행하면 고인물의 양을 계산할 수 있다.

• 먼저 높이 2를 갖는 h[0]의 인덱스 0를 push한다. 스택은 {[0]}
• 그다음 h[1]높이가 top보다 작으므로 h[1]인덱스를 push 스택은 {[0], [1]}
• 그다음 h[2]높이가 top보다 작으므로 h[2]인덱스를 push 스택은 {[0], [1], [2]}
• 그 다음 h[3]높이가 top보다 크다. 따라서 top위치(h[2])에는 물이 고일것이다. 물이 고이는 높이는 h[3]과 스택내의 top바로 직전 높이 h[1]중에 작은 높이가 될것이다. 그리고 폭은 인덱스값 차이인 [3] - [1] - 1가 되어 높이*폭 = 1이 된다. 이 작업을 수행하면 아래와 같이 물이 고인다. 이 시점에 스택은 한번 pop되었기 때문에 {[0], [1]}

       ⬛️   
  ⬛️    ⬛️  
  ⬛️⬛️⬜️⬛️
  ⬛️⬛️⬛️⬛️

• 현재 비교 대상인 h[3]의 높이가 여전히 스택 top값인 h[1]보다 높다. 따라서 pop및 위의 계산을 또 한번 수행한다. 높이: min(h[3], h[0]) - h[1], 그리고 폭은: [3]-[0]-1. 높이는 1 (2-1), 폭은 2, 따라서 물의 양은 2가 추가된다. 이 시점이 되면 아래와 같이 물이 추가로 찬다. 스택은 모두 pop이 되고, 현재 높이 h[3]이 push된다. 따라서 스택은 {[3]}

       ⬛️   
  ⬛️⬜️⬜️⬛️  
  ⬛️⬛️⬜️⬛️
  ⬛️⬛️⬛️⬛️

이어지는 높이가 주어져도 이 동작을 반복하면 고인물의 총량을 계산할 수 있다.
해설을 참고하였는데, 이 풀이를 이해 하는데 꽤나 오래걸렸다.

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st; // index
        int hsize = height.size();
        int amount_water = 0;
        
        for (int i = 0; i < hsize; i++) {
            // if curr height >= then top of stack
            while (!st.empty() && height[i] >= height[st.top()]) {
                // -_-
                // 123   -> (3): curr height[i], (2): first st.top(), (3): second st.top()
                int u_shape_idx = st.top(); // the first st.top() is always 'U' shape position 
                st.pop();
                if (st.empty())
                    break;
                // this point st.top()'s height is always higher than height[u_shape_idx]
                int distance = i - st.top() - 1;
                int water_height = std::min(height[i], height[st.top()]) - height[u_shape_idx];
                amount_water += distance * water_height;
            }
            st.push(i);
        }
        return amount_water;
    }
};

해결 - Two Pointer - O(n) / O(1)