빗물 트래핑 LeetCode Solution

난이도 하드
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 데이터 브릭 Expedia Facebook Flipkart 골드만 삭스 구글 Microsoft 신탁 Qualtrics ServiceNow 테슬라 월마트 연구소 Yahoo
배열 스택 두 포인터조회수 58

Trapping Rain Water LeetCode 문제에서 고도 지도를 나타내는 N개의 음이 아닌 정수를 제공했으며 각 막대의 너비는 1입니다. 위의 구조에서 갇힐 수 있는 물의 양을 찾아야 합니다.

예를 들어 이해합시다

빗물 잡기

위 고도지도의 경우

입력

[2,1,0,2,2,0,1,4]

산출

6

더 많은 테스트 사례를 살펴 보겠습니다.

입력

[0,1,0,2,1,0,1,3,2,1,2,1]

산출

6

트 랩핑 빗물을 찾기위한 접근법 -1

브 루트 포스

  • 모든 요소를 정렬
  • 왼쪽에서 최대 높이 구하기 = L
  • 오른쪽에서 최대 높이 찾기 = R
  • 저장할 수있는 최대 물의 양 = 최소 (L, R)-요소 높이

Java와 C ++에서 동일한 코드를 살펴 보겠습니다.

빗물 트랩을위한 자바 프로그램

class Solution 
{
    public int trap(int[] height)
    {
    if(height==null)
        return 0;
    int ans=0;
    for(int i=1;i<height.length-1;i++)
    {
        int l=Integer.MIN_VALUE;
        int r=Integer.MIN_VALUE;
        for(int j=0;j<i+1;j++)
            l=Math.max(l,height[j]);
        for(int j=i;j<height.length;j++)
            r=Math.max(r,height[j]);
        ans=ans+Math.min(l,r)-height[i];
    }
    return ans;
    }
}

빗물 트랩을위한 C ++ 프로그램

class Solution 
{
public:
    int max(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int min(int a,int b)
    {
        if(b>a)
            return a;
        else
            return b;
    }
public:
    int trap(vector<int>& height)
    {
    if(height.size()==0) 
        return 0; 
    int ans=0; 
    int i,j;
    for(i=1;i<height.size()-1;i++) 
    { 
      int l=-1; 
      int r=-1; 
      for(j=0;j<i+1;j++) 
      l=max(l,height[j]); 
      for(j=i;j<height.size();j++)
      r=max(r,height[j]); 
      ans=ans+min(l,r)-height[i]; 
    } 
    return ans;    
    }
};
[2,1,0,2,2,0,1,4]
6

복잡성 분석

위의 시간 복잡도는 O (n ^ 2)로 계산할 수 있습니다.

트 랩핑 빗물을 찾기위한 접근법 -2

동적 프로그래밍

전체 부분을 반복하는 대신 지점까지 가장 높은 블록의 높이를 각 배열에 저장할 수 있습니다.

코드를 살펴 보겠습니다.

자바 프로그램

class Solution 
{
    public int trap(int[] height)
    {
    if(height.length==0)
        return 0;
    int ans=0;
    //left[i] contains the maximum height of the pillar encountered before the ith pillar
    int left[]=new int[height.length];
    left[0]=height[0];
    //righ[i] contains the maximum height of the pillar encountered after the ith pillar
    int righ[]=new int[height.length];
    righ[righ.length-1]=height[height.length-1];
    for(int i=1;i<height.length;i++)
    {
      left[i]=Math.max(height[i],left[i-1]);
    }
    for(int i=height.length-2;i>-1;i--)
    {
        righ[i]=Math.max(height[i],righ[i+1]);
    }
    for(int i=1;i<height.length-1;i++)
    {
        ans=ans+Math.min(left[i],righ[i])-height[i];
    }
    return ans;
    }
}

C ++ 프로그램

class Solution 
{
public:
    int max(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int min(int a,int b)
    {
        if(b>a)
            return a;
        else
            return b;
    }
public:
    int trap(vector<int>& height)
    {
    if(height.size()==0)
        return 0;
    int ans=0;
    int left[height.size()];
    left[0]=height[0];
    int righ[height.size()];
    righ[height.size()-1]=height[height.size()-1];
    for(int i=1;i<height.size();i++)
    {
      left[i]=max(height[i],left[i-1]);
    }
    for(int i=height.size()-2;i>-1;i--)
    {
        righ[i]=max(height[i],righ[i+1]);
    }
    for(int i=1;i<height.size()-1;i++)
    {
        ans=ans+min(left[i],righ[i])-height[i];
    }
    return ans;   
    }
};
[0,1,0,2,1,0,1,3,2,1,2,1]
6

트 랩핑 빗물을 찾기위한 접근법 -3

두 포인터 접근

이전 접근 방식에서 관찰 한 내용을 살펴 보겠습니다.

  • right_max가 left_max보다 크면 우리는 갇힌 물의 양을 찾기 위해 left_max에 의존합니다.
  • left_max가 right_max보다 큰 한 right_max에 의존하여 갇힌 물의 양을 찾습니다.

따라서 왼쪽 및 오른쪽 배열을 유지하는 대신 두 개의 포인터를 유지합니다.

코드의 도움으로 더 잘 이해합시다.

자바 프로그램

class Solution 
{
    public int trap(int[] height)
    {
      int left=0;
      int righ=height.length-1;
      int lmax=Integer.MIN_VALUE;
      int rmax=Integer.MIN_VALUE;
      int ans=0;
      while(righ>left)
      {
          //We rely on the minimum of the both
          if(height[left]<height[righ])
          {
          //Update left max if the current height is greater
          if(height[left]>=lmax)
              lmax=height[left];
          //else add the water trapped to the answer
          else
          ans=ans+lmax-height[left];
          left=left+1;
          }
          else
          {
          //If current height is greater than right max update
          if(height[righ]>=rmax)
              rmax=height[righ];
          //else add to the answer
          else
          ans=ans+rmax-height[righ]; 
          righ=righ-1;
          }
      }
    return ans;
    }
}

C ++ 프로그램

class Solution 
{
public:
    int max(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int min(int a,int b)
    {
        if(b>a)
            return a;
        else
            return b;
    }
public:
    int trap(vector<int>& height)
    {
    int left=0; 
    int righ=height.size()-1; 
    int lmax=-1; 
    int rmax=-1; 
    int ans=0; 
    while(righ>left) 
    { 
        //We rely on the minimum of the both 
        if(height[left]<height[righ]) 
        { //Update left max if the current height is greater 
            if(height[left]>=lmax) 
                lmax=height[left]; 
            //else add the water trapped to the answer 
            else ans=ans+lmax-height[left]; left=left+1; 
        } 
        else 
        { //If current height is greater than right max update 
            if(height[righ]>=rmax) 
                rmax=height[righ]; 
            //else add to the answer 
            else 
                ans=ans+rmax-height[righ]; 
            righ=righ-1; 
        }
       }
    return ans;
    }
};
[ 8, 0, 8 ]
8

복잡성 분석

  • 위 솔루션의 시간 복잡도 = O (n)
  • 여기서 보조 공간을 사용하지 않기 때문에 공간 복잡도 = O (1)입니다.

따라서 빗물을 가두는 문제와이를 해결하기위한 다양한 접근 방식이었습니다!

참조

Translate »
1