Yağış Suyu LeetCode Tutma problemində biz hündürlük xəritəsini təmsil edən N qeyri-mənfi tam ədəd verdik və hər bir çubuğun eni 1-dir. Biz yuxarıdakı strukturda tutula biləcək suyun miqdarını tapmalıyıq.
Mündəricat
misal
Bunu bir nümunə ilə başa düşək
Yuxarıdakı yüksəklik xəritəsi üçün
Input
[2,1,0,2,2,0,1,4]
Buraxılış
6
Daha bir neçə sınaq işinə baxaq:
Input
[0,1,0,2,1,0,1,3,2,1,2,1]
Buraxılış
6
Yağış suyunu tutmağı tapmaq üçün yanaşma-1
Brute Force
- Hər elementi keçin array
- Soldan maksimum hündürlüyü tapın = L
- Sağdan maksimum hündürlüyü tapın = R
- Saxlanıla bilən maksimum su miqdarı = min (L, R) - elementin hündürlüyü
Gəlin Java və C ++ dillərində olanların kodunu nəzərdən keçirək.
Yağış suyunu tutmaq üçün Java proqramı
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;
}
}
Yağış Suyu Tutmaq üçün C ++ Proqramı
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
Mürəkkəblik təhlili
Yuxarıda göstərilənlərin vaxt mürəkkəbliyi O (n ^ 2) olaraq hesablana bilər.
Yağış suyunu tutmağı tapmaq üçün yanaşma-2
Dinamik proqramlaşdırma
Bütün hissələr üzərində təkrarlamaqdansa, ən yüksək blokun nöqtəyə qədər hündürlüyü müvafiq massivlərdə saxlanıla bilər.
Kodu nəzərdən keçirək
Java Proqramı
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 ++ Proqramı
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
Yağış suyunu tutmağı tapmaq üçün yanaşma-3
İki işarəçi yanaşma
Əvvəlki yanaşmadan müşahidələrə nəzər salaq
- Right_max left_max-dan böyük olduğu müddətdə, tələyə düşən suyun miqdarını tapmaq üçün left_max-dan asılıyıq.
- Sol_max right_max-dan böyük olduğu müddətdə, tutulan suyun miqdarını tapmaq üçün right_max-dan asılı oluruq.
Beləliklə, sol və sağ massivi qorumaq əvəzinə iki göstəricini saxlayırıq.
Bir kodun köməyi ilə daha yaxşı başa düşək.
Java Proqramı
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 ++ Proqramı
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
Mürəkkəblik təhlili
- Yuxarıdakı həllin zaman mürəkkəbliyi = O (n)
- Kosmik mürəkkəblik = O (1), çünki burada heç bir köməkçi yer istifadə etmirik.
Beləliklə, bu tələyə düşən yağış suyu problemi və həllinə bir çox yanaşma idi!
