Trapping Rain Water
题目大意
给你一个非负的数组，假设其宽度为1，试问按如下规则能装多少水：
我的解法&优解
解题思路
如下图所示，最终的临界点，从左到最高点和从右到最高点，一定是递增的。因此，从两端往中间遍历即可。
代码
class Solution {
public:
int trap(vector<
int>& height) {
int left_max =
0;
int right_max =
0;
int left =
0;
int right = height.size() -
1;
int container =
0;
while(
left<=
right)
{
if(left_max > right_max)
{
if(height[
right] > right_max)
{
right_max = height[
right];
}
else
{
container += right_max - height[
right];
}
right--;
}
else
{
if(height[
left] > left_max)
{
left_max = height[
left];
}
else
{
container += left_max - height[
left];
}
left++;
}
}
return container;
}
};
