42. Trapping Rain Water
Problem's Link
----------------------------------------------------------------------------
Mean:
在坐标上给你一些竖直放置的条形积木，问你这个积木能够容纳多少液体.
analyse:
首先找出最高的积木，然后从前往后一直扫到最高积木，从后往前一直扫到最高积木，两部分体积相加即可.
Time complexity: O(N)
view code
;
;
;;
;
);
;
;
);;
}
/*
;
;;
;
);
;
;
);;
}
/*
*/
2.方法二：时间O(n),空间(1)
;
;
;
while(left<right)
{
if(height[left]<=height[right])
{
if(height[left]>maxLeft)
maxLeft=height[left];
res+=maxLeft-height[left];
left++;
}
else
{
if(height[right]>maxRight)
maxRight=height[right];
res+=maxRight-height[right];
right--;
}
}
return res;
}
};
;
;
while(left<right)
{
if(height[left]<=height[right])
{
if(height[left]>maxLeft)
maxLeft=height[left];
res+=maxLeft-height[left];
left++;
}
else
{
if(height[right]>maxRight)
maxRight=height[right];
res+=maxRight-height[right];
right--;
}
}
return res;
}
};