博文中会简要介绍Leetcode P0042题目分析及解题思路。
“Trapping Rain Water”是一道非常经典的问题，在很多面试中都会出现，也属于原型题之一。这篇博文主要介绍动态规划的做法，比较简单直接。C++代码实现了使用栈（单调栈）的解法，有一些具体注释，这里不再赘述。使用栈的解法相对于用动态规划的解法，在思维上相对要复杂一些。
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
下面重点讲解动态规划的思路。仔细读题后我们不难发现，想要得到以某一个bar为底座的储水量，需要知道这个bar左边最高的高度和右边最高的高度，然后取这两个高度中的较小值，用这个较小值与当前这个bar的高度作差就能得到这个bar为底座的储水量了。
为什么需要知道左右端的最大高度呢？
原因其实很简单，如果我们假定右端高度无穷大，那么左端的高度越高，以该bar为底座，宽度为1的上方的储水量也就越多，也就是说储水量取决于左端（也是较小端，因为右端高度是无穷大），同理右端，所以找到左右端最大高度。而实际的储水量则取决于这两个高度中的较小值，也是前面说到的取决于较小端。于是我们就得到了计算储水量的方法。
那么如何快速地得到左右两端的最大值呢？我们可以使用动态规划的思维，即一个bar左端的最大值一定等于这个bar前面一个bar的左端最大值和这个bar自身的高度中的较大值，也即：
leftMax[i] = max(height[i], leftMax[i-1]);
这样一来我们就得到每个bar左端的最大高度，同理我们也可以得到每个bar右端的最大值，然后计算储水量，使用两端最大高度中的较小值作为实际水面即可。
以下是Java的题解代码实现。
class Solution {
public int trap(int[] height) {
if (height == null || height.length == 0)
return 0;
int[] cover = new int[height.length];
int leftMax = height[0];
for (int idx=1; idx<height.length; ++idx) {
if (height[idx] > leftMax) {
leftMax = height[idx];
}
cover[idx] = leftMax;
}
int rightMax = height[height.length-1];
int trapped = 0;
for (int idx=height.length-2; idx>0; --idx) {
if (height[idx] > rightMax) {
rightMax = height[idx];
}
trapped += (Math.min(rightMax, cover[idx])-height[idx]);
}
return trapped;
}
}
以下是实现了单调栈解法的C++题解代码实现。
class Solution {
public:
int trap(vector<int>& height) {
int trapped_water = 0, current = 0;
stack<int> st;
while (current < height.size()) {
// 若栈顶bar高较大，则将当前较小bar塞入栈中，成为底座；反之则开始计算储水量
// 如果栈非空，并且栈顶小于当前bar高，则有装水可能，寻找到最左边的bar直到栈空或者栈顶更高
while (!st.empty() && height[current] > height[st.top()]) {
int top = st.top();
st.pop();
// 若栈空说明左端bar已经出栈，没有左端bar拦水，则不用再计算储水量
if (st.empty())
break;
// 计算当前bar的位置到左端bar位置的宽度
int distance = current-st.top()-1;
// 计算当前左右端的bar所限定的区域内的水面高度和当前底座高度的差
int bounded_height = min(height[current], height[st.top()]) - height[top];
trapped_water += distance * bounded_height;
}
st.push(current);
++current;
}
return trapped_water;
}
};