故园便是无兵马
犹有归时一段愁
这道题，我记得去年9月份的时候就见过，但是当时想了一会没想出来就算了，现在还是碰到了。
要能够解这道题，需要转化一下思路，从现实实际着手，而不是死磕套路，这样一下子反而想不起来套路。
这道题如果放现实里就是计算水的体积，只是这里将水坑作了简化，水坑由一块块宽度为1的砖块组成。实际上如果我们在现实生活中计算这个体积，或者是数学题里，会很快想到要求出水面的高度。。。反而在这种题目里会有点蒙圈，就是套路题做多了，一下子套不上。。。
所以重点就是，如果得出水面的高度。
一个点的水面的高度，应该等于对应水坑左右两端的较低端的高度，记为leftmax和rightmax也就是往左往右找两个最高点，两个最高点中找一下较低的，就是水面的高度！
理解了这个这个思路后，就相当简单，很快就能写出O(N^2)的代码了，for里面套两个for就完事。。。
但显然这样子不科学，出现了很多的重复计算，实际上我们可以在大循环外，用一个循环将每个点对应的左端点和右端点计算出来存起来，这样直接能得到每个点的水面高度！
class Solution {
public:
int trap(vector<int>& height) {
int m = height.size();
std::vector<int> leftmax(m, 0), rightmax(m, 0);
int maxele = 0;
for (int i = 0; i < m; i++) {
maxele = max(height[i], maxele);
leftmax[i] = maxele;
}
maxele = 0;
for (int i = m - 1; i >= 0; i--) {
maxele = max(height[i], maxele);
rightmax[i] = maxele;
}
int ans = 0;
for (int i = 0; i < m; i++) {
int level = min(leftmax[i], rightmax[i]);
ans += (level > height[i]) ? (level - height[i]) : 0;
}
return ans;
}
};
