1A
c++
O(n^2)
class Solution {
public:
int trap(vector<int>& height) {
int ans=0;
for(int i=1;i<height.size();i++)
{
if(height[i]>height[i-1])
{
int pos=0;
for(int j=i-2;j>=0;j--)
{
if(height[j+1]<height[j])
{
int h=min(height[j],height[i]);
for(int k=j+1;k<=i-1;k++)
{
ans += h-height[k];
height[k] += h-height[k];
}
if(height[i]<height[j])
break;
}
}
}
}
return ans;
}
};O(n)
class Solution {
public:
int left[100005];
int right[100005];
int trap(vector<int>& height) {
int ans=0;
if(height.size()==0)
return ans;
left[0] = height[0];
for(int i=1;i<height.size();i++)
{
left[i] = max(left[i-1],height[i]);
}
right[height.size()-1] = height[height.size()-1];
for(int j=height.size()-2;j>=0;j--)
{
right[j]=max(right[j+1],height[j]);
}
for(int i=0;i<height.size();i++)
{
ans += min(left[i],right[i]) - height[i];
}
return ans;
}
};