빗물 가두기 🌊

오늘의 질문:

비가 오는 날이고 너비가 각각 1단위인 n개의 막대가 주어집니다. 그들 사이에 갇힌 물의 양을 어떻게 계산할 것입니까? 🌧️

First try to solve the problem here: https://leetcode.com/problems/trapping-rain-water/

갇힌? 🤔

걱정 마세요, 제가 책임져드리겠습니다!!

생각해보자💭

비가 내린 후 얼마나 많은 물 유닛이 갇히게 될지 알아내야 합니다...어떻게 할 수 있을까요?

총 물은 각 막대에 저장된 개별 물을 계산하고 합산할 수 있음을 의미합니다. 맞나요?

예, 저장된 개별 물을 계산하려면 물이 어느 막대에서 어느 막대에 저장되고 있는지 알아야 합니다... 요소의 양쪽에서 최대 막대를 찾을 수 있습니까?

예! 왼쪽 최대 및 오른쪽 최대

그러나 leftMax와 rightMax 중 큰 것의 높이까지는 물이 갇히지 않습니다.

따라서 최소값(leftMax, rightMax)을 가져와야 합니다.

그리고 우리는 갇힌 물의 양을 찾으려고 하기 때문에 물이 갇힐 각 막대의 남은 높이를 알아야 합니다.

따라서 각 막대의 최소값(leftMax, rightMax)에서 막대의 높이를 뺀 다음 합산하여 총 물을 얻습니다.

연산:

주어진 막대의 왼쪽과 측면 부분을 최대로 가져옵니다.

min(leftMax, rightMax) - bar[i]로 각 막대의 물을 가져옵니다.

물을 요약하십시오.

int trap(vector<int>& height) {

        int n = height.size(); 
        int waterSum = 0;
        for(int i=0; i<n; i++){

            int leftMax = 0, rightMax = 0;
            for(int j=i; j>=0; j--){
                leftMax = max(leftMax,height[j]);
            }

            for(int j=i; j<n; j++){
                rightMax = max(rightMax,height[j]);
            }

            int h = min(leftMax,rightMax); 
            waterSum+=h-height[i];
        }

        return waterSum;
    }

복잡성: 시간: O(N*N) 공간: O(1)

이 솔루션에서는 시간 복잡도가 증가하고 있습니다. 이를 줄이기 위해 다음과 같이 leftMax와 rightMax를 별도의 배열에 저장할 수 있습니다.

int trap(vector<int>& height) {

        int n = height.size();
        vector<int> water;

        vector<int> l(n);
        vector<int> r(n);
        l[0]=height[0];
        r[n-1]=height[n-1];

        for(int i=1; i<n; i++){
            l[i]=max(l[i-1],height[i]);
        }

        for(int i=n-2; i>=0; i--){
            r[i]=max(r[i+1],height[i]);
        }

        for(int i=0; i<n; i++){
            int a = min(l[i],r[i]);
            water.push_back(a-height[i]);
        }

        int x = accumulate(water.begin(),water.end(),0);
        return x;
    }

복잡성: 시간: O(N) 공간: O(N)

이를 더 최적화하기 위해 공간 복잡도를 O(N)에서 O(1)로 만들 수 있습니다.

우리는 이것을 어떻게 할 것입니까?

2점 접근 방식을 사용할 수 있습니다. 여기에서 왼쪽 포인터는 배열의 시작 부분에 있고 오른쪽 포인터는 끝에 있습니다.

왼쪽 요소가 오른쪽 요소보다 작거나 같을 때마다 두 가지 옵션이 있습니다.

왼쪽에서 최대값인지 확인합니다. 그렇다면 leftMax를 업데이트하십시오. 그렇지 않으면

오른쪽에는 height[left]보다 큰 막대가 항상 있기 때문에 height[left]를 빼서 ans로 합산할 수 있습니다.

오른쪽 요소가 왼쪽 요소보다 작은 경우 오른쪽에 대해 동일한 두 가지 옵션을 수행할 수 있습니다.

 int trap(vector<int>& height) {

        int n = height.size();
        int leftMax = 0, rightMax = 0, left=0, right=n-1, ans=0;

        while(left<=right){

            if(height[left]<=height[right]){
                if(leftMax<= height[left]){
                    leftMax= height[left];
                } else{
                    ans +=leftMax-height[left];
                }
                left++;
            } 
            else{
                if(height[right]>=rightMax){
                    rightMax = height[right];
                } else{
                    ans +=rightMax-height[right];
                }
                 right--;
            }
        }
        return ans;
    }

복잡성: 시간: O(N) 공간: O(1)

이것이 전부입니다! 끝까지 읽어주셔서 감사합니다. 😃

Synopsis:

For brute force, find the maximum of both sides and sum it for each bar.

A better approach would be to store the left and right maximums in separate arrays.

Two-pointer is the best approach.

✒ 내 블로그가 처음이신가요?

여기요! 저는 카나크입니다.

저는 MERN 스택 개발자이자 오픈 소스 애호가입니다. 저는 데이터 구조와 알고리즘에 대해 글을 쓰고 DSA 주제에 대한 치트 시트를 개발합니다. 또한 지난 2개월 동안 Twitter에 내 DSA 여정을 문서화했습니다.

더 많은 콘텐츠를 보려면 저를 팔로우하세요. 🎉