[LeetCode] 42. Trapping Rain Water

문제 URL : https://leetcode.com/problems/trapping-rain-water/

Trapping Rain Water - LeetCode

 

문제접근법 : 검은 블록이 쌓였는곳에 물을 부었을대 얼마만큼 차는지 확인하는 문제입니다.

 

처음에 기준점을 찾았는데 왼쪽에서 오른쪽으로 막대가 커지는 막대가 커지는지 확인하고

반대로 오른쪽에서 왼쪽으로 막대가 커지는지 확인하다보면 

결국엔 왼쪽과 오른쪽 막대가 긴막대에따라서 물이 잠겨지게됩니다.

 

왼쪽에서부터 큰막대의 높이를 저장하는배열을 lv

오른족에서부터 큰막대를 저장하는 배열을 rv라할때

min(lv[i],rv[i])-height 를 하면 물이 얼마만큼 잠기는지 알수있습니다.

소스코드 : 

class Solution {
public:
int trap(vector<int>& height) {
    int res=0;
    int n = height.size();
    vector<int> lv(n),rv(n);
    lv[0]=height[0];
    for(int i=1;i<n;i++)lv[i]=max(lv[i-1],height[i]);
    rv[n-1]=height[n-1];
    for(int i=n-2;i>=0;i--)rv[i]=max(rv[i+1],height[i]);
    
    for(int i=0;i<n;i++){
        res+=min(lv[i],rv[i])-height[i];
    }
    return res;
}
};