C++ ] leetCode 42 - Trapping Rain Water

 

 

리트코드 42번 문제

 

 

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
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

 

 

 

이 문제는 stack을 사용해서 풀 수 있는 문제인데 739번 Daily Temperatures와 비슷한 방식으로 풀 수 있다.

 

먼저 배열을 순회하면서 스택에 현재 인덱스를 넣고, 순회 도중 현재 인덱스의 높이가 스택의 최상단 요소의 높이보다 높다면 꺼내서 물이 채워질 수 있는 영역인지, 채워질 수 있다면 해당 영역의 너비가 어떻게 되는지 계산해 답에 더한다.

 

 

현재 인덱스의 높이가 스택의 최상단 요소의 높이보다 높은 동안은 다음 과정을 반복적으로 수행한다.

 

1. 스택에서 현재 최상단 요소를 확인하고 pop한다.
2. 스택에 이전 최상단 요소가 들어있지 않은 경우 물이 채워질 수 없기 때문에 break;로 탈출한다.
   (이전 최상단 요소의 높이가 현재 최상단 요소의 높이보다 작거나 같거나 영역의 Width가 0인 경우 continue;로 돌아가서 조건 검사하고 스택의 다음요소를 꺼내 처리하게끔 할 수 있긴한데 성능에 유의미한 차이는 없었따.)
3. '현재 인덱스' - '현재 최상단 요소' - 1로 영역의 width를 확인한다.
4. '현재 인덱스의 높이와 이전 최상단 요소의 높이 중 작은 값' - '현재 최상단 요소의 높이'로 영역의 height를 확인한다.
5. 리턴값에 영역의 너비를 더한다.

 

 

 

 

 

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

class Solution {
public:
    int trap(vector<int>& height) {
        int ret = 0;
        stack<int> s;
        
        for(int i = 0; i < height.size(); i++) {
            while(!s.empty() && (height[i] > height[s.top()])) {
                int top = s.top();
                s.pop();
                if(s.empty()) break;
                int boxWidth = i - s.top() - 1;
                int boxHeight = min(height[i], height[s.top()]) - height[top];
                ret += boxWidth * boxHeight;
            }
            s.push(i);
        }
        
        return ret;
    }
};

int main() {
    Solution solution;
    vector<int> Example1 = {0,1,0,2,1,0,1,3,2,1,2,1};
    cout << solution.trap(Example1) << endl;
    
    vector<int> Example2 = {4,2,0,3,2,5};
    cout << solution.trap(Example2) << endl;

    return 0;
}