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.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
这道收集雨水的题跟之前的那道 Largest Rectangle in Histogram 直方图中最大的矩形 有些类似，但是又不太一样，我们先来看一种方法，这种方法是基于动态规划Dynamic Programming的，我们维护一个一维的dp数组，这个DP算法需要遍历两遍数组，第一遍遍历dp[i]中存入i位置左边的最大值，然后开始第二遍遍历数组，第二次遍历时找右边最大值，然后和左边最大值比较取其中的较小值，然后跟当前值A[i]相比，如果大于当前值，则将差值存入结果，代码如下：
C++ 解法一：
class Solution { public: int trap(vector<int>& height) { int res = 0, mx = 0, n = height.size(); vector<int> dp(n, 0); for (int i = 0; i < n; ++i) { dp[i] = mx; mx = max(mx, height[i]); } mx = 0; for (int i = n - 1; i >= 0; --i) { dp[i] = min(dp[i], mx); mx = max(mx, height[i]); if (dp[i] > height[i]) res += dp[i] - height[i]; } return res; } };
Java 解法一：
public class Solution { public int trap(int[] height) { int res = 0, mx = 0, n = height.length; int[] dp = new int[n]; for (int i = 0; i < n; ++i) { dp[i] = mx; mx = Math.max(mx, height[i]); } mx = 0; for (int i = n - 1; i >= 0; --i) { dp[i] = Math.min(dp[i], mx); mx = Math.max(mx, height[i]); if (dp[i] - height[i] > 0) res += dp[i] - height[i]; } return res; } }
最后我们来看一种只需要遍历一次即可的解法，这个算法需要left和right两个指针分别指向数组的首尾位置，从两边向中间扫描，在当前两指针确定的范围内，先比较两头找出较小值，如果较小值是left指向的值，则从左向右扫描，如果较小值是right指向的值，则从右向左扫描，若遇到的值比当较小值小，则将差值存入结果，如遇到的值大，则重新确定新的窗口范围，以此类推直至left和right指针重合，具体参见代码如下：
C++ 解法二：
class Solution { public: int trap(vector<int>& height) { int res = 0, l = 0, r = height.size() - 1; while (l < r) { int mn = min(height[l], height[r]); if (mn == height[l]) { ++l; while (l < r && height[l] < mn) { res += mn - height[l++]; } } else { --r; while (l < r && height[r] < mn) { res += mn - height[r--]; } } } return res; } };
Java 解法二：
public class Solution { public int trap(int[] height) { int res = 0, l = 0, r = height.length - 1; while (l < r) { int mn = Math.min(height[l], height[r]); if (height[l] == mn) { ++l; while (l < r && height[l] < mn) { res += mn - height[l++]; } } else { --r; while (l < r && height[r] < mn) { res += mn - height[r--]; } } } return res; } }
我们可以对上面的解法进行进一步优化，使其更加简介：
C++ 解法三：
class Solution { public: int trap(vector<int>& height) { int l = 0, r = height.size() - 1, level = 0, res = 0; while (l < r) { int lower = height[(height[l] < height[r]) ? l++ : r--]; level = max(level, lower); res += level - lower; } return res; } };
Java 解法三：
public class Solution { public int trap(int[] height) { int l = 0, r = height.length - 1, level = 0, res = 0; while (l < r) { int lower = height[(height[l] < height[r]) ? l++ : r--]; level = Math.max(level, lower); res += level - lower; } return res; } }
下面这种解法是用stack来做的，博主一开始都没有注意到这道题的tag还有stack，所以以后在总结的时候还是要多多留意一下标签啊。其实用stack的方法博主感觉更容易理解，我们的做法是，遍历高度，如果此时栈为空，或者当前高度小于等于栈顶高度，则把当前高度的坐标压入栈，注意我们不直接把高度压入栈，而是把坐标压入栈，这样方便我们在后来算水平距离。当我们遇到比栈顶高度大的时候，就说明有可能会有坑存在，可以装雨水。此时我们栈里至少有一个高度，如果只有一个的话，那么不能形成坑，我们直接跳过，如果多余一个的话，那么此时把栈顶元素取出来当作坑，新的栈顶元素就是左边界，当前高度是右边界，只要取二者较小的，减去坑的高度，长度就是右边界坐标减去左边界坐标再减1，二者相乘就是盛水量啦，参见代码如下：
C++ 解法四：
class Solution { public: int trap(vector<int>& height) { stack<int> st; int i = 0, res = 0, n = height.size(); while (i < n) { if (st.empty() || height[i] <= height[st.top()]) { st.push(i++); } else { int t = st.top(); st.pop(); if (st.empty()) continue; res += (min(height[i], height[st.top()]) - height[t]) * (i - st.top() - 1); } } return res; } };
Java 解法四：
class Solution { public int trap(int[] height) { Stack<Integer> s = new Stack<Integer>(); int i = 0, n = height.length, res = 0; while (i < n) { if (s.isEmpty() || height[i] <= height[s.peek()]) { s.push(i++); } else { int t = s.pop(); if (s.isEmpty()) continue; res += (Math.min(height[i], height[s.peek()]) - height[t]) * (i - s.peek() - 1); } } return res; } }
本文转自博客园Grandyang的博客，原文链接：收集雨水[LeetCode] Trapping Rain Water ，如需转载请自行联系原博主。
