[LeetCode] 42. Trapping Rain Water

https://leetcode.com/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-interview-150 

Trapping Rain Water - LeetCode

문제 유형 : 투 포인터

문제 난이도 : Hard

 

문제

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.

 

음수가 아닌 정수가 n개 주어지고, 이는 높이를 의미합니다. 각 높이간의 너비는 1입니다.

비가 내렸을 때 쌓이는 양을 구하시오.

 

풀이

비가 얼마나 내리든, 비가 최대한 모이는 양은 가장 낮은 벽까지만 차오릅니다.

그래서 왼쪽과 오른쪽에서 탐색을 시작하며, 각 쪽에서 최대 높이를 구하고, 만약에 최대 높이가 갱신되지 않는다면 왼쪽과 오른쪽의 최대값중 최소값에서 현재의 높이를 빼면 그 공간의 차는 물의 양이 됩니다.

 

left가 right보다 커지면 탐색을 멈춥니다. 이 코드는 선형 시간복잡도를 가집니다.

 

코드(C++)

class Solution {
public:
    int trap(vector<int>& height) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);

        const int n = height.size();
        int left = 0
        int right = n - 1;
        int maxLeft = 0
        int maxRight = 0;
        int trapped = 0;
        
        while(left < right){
            if(height[left] <= height[right]){
                if(height[left] >= maxLeft) 
                    maxLeft = height[left];
                else 
                    trapped += maxLeft - height[left];
                left++;
            }else{
                if(height[right] >= maxRight)
                    maxRight = height[right];
                else 
                    trapped += maxRight - height[right];
                right--;
            }
        }
        return trapped;
    }
};