# 题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
# 思路
可以通过左右双指针来解决该题目。l 从数组最左边遍历，r 从数组最右边遍历，并且维护一个 lmax 和 rmax（这两个变量可以合并成一个变量）。比较 height [l] 和 height [r] 获取最低的所在方向，若方向改变，更新 base 值，执行 l 或 r--；若不变，则计算 result += height [l] 或 height [r] - base，然后执行 l 或 r--。最后当 l>=r 时结束返回结果，该解决方法时间复杂度 O (n)，空间复杂度为常数级。
# 题解
class Solution { | |
public: | |
int trap(vector<int>& height) { | |
if (height.size() == 1) return 0; | |
if (height.size() == 2) return 0; | |
int l = 0, r = height.size() - 1, base = height[l]; | |
int result = 0; | |
bool left = true; | |
while (l < r) { | |
if (height[l] <= height[r]) { | |
if (left) { | |
if (base > height[l]) { | |
result += base - height[l]; | |
} else { | |
base = height[l]; | |
} | |
} else { | |
left = true; | |
base = height[l]; | |
} | |
l++; | |
} else { | |
if (left) { | |
left = false; | |
base = height[r]; | |
} else { | |
if (base > height[r]) { | |
result += base - height[r]; | |
} else { | |
base = height[r]; | |
} | |
} | |
r--; | |
} | |
} | |
return result; | |
} | |
}; |
