[LeetCode]Trapping Rain Water

首先这种两边决定当前位置的值的题，很容易想到要用双向dp来做，就是从左到右一次，从右到左一次，然后根据两边的限制来算当前的值。那么这一题我们要的是当前位置左边和右边的最高值，这样用左边和右边最高值的较小值来减去当前的高度就是这个单位长度能盛水的面积。注意我们第二次dp和计算可以和在一起，并且第二次dp不需要维护arr，维护一个滚动变量就可以，扫两遍，时间复杂度O(n)，开一个数组，空间复杂度O(n)，代码如下：

	public class Solution {
	public int trap(int[] A) {
	if (A == null)
	return 0;
	int len = A.length;
	if (len < 3)
	return 0;
	int[] left = new int[len];
	int right = 0, sum = 0;
	for (int i = 1; i < len; i++)
	left[i] = A[i - 1] >= left[i - 1]? A[i - 1]: left[i - 1];
	for (int i = len - 2; i >= 0; i--) {
	right = A[i + 1] >= right? A[i + 1]: right;
	int height = left[i] <= right? left[i]: right;
	int area = A[i] >= height? 0: height - A[i];
	sum += area;
	}
	return sum;
	}
	}

view raw trapping rain water v-1.java hosted with ❤ by GitHub

第二种方法是双指针，比如现在i指向的高度小于j指向的高度，那么从i开始右边的连续递减子序列是肯定可以存水的，并且存水的高度等于i的高度，因为右边必定是有一个高度大于i的高度的墙壁可以挡住水。对于右边也是一样的。时间复杂度O(n)，空间复杂度O(1)，我们用f[i]表示到i位置左边最高的墙的高度，DP方程为：

• f[i] = max(f[i - 1], A[i - 1]);
• f[0] = 0;

代码如下：

	public class Solution {
	public int trap(int[] A) {
	if (A == null)
	return 0;
	int len = A.length, left = 0, right = len - 1, sum = 0;
	while (left < right) {
	int l = A[left];
	int r = A[right];
	if (l <= r) {
	while (left < right && A[++left] < l)
	sum += l - A[left];
	} else {
	while (left < right && A[--right] < r)
	sum += r - A[right];
	}
	}
	return sum;
	}
	}

view raw trapping rain water v-2.java hosted with ❤ by GitHub

最后还有一种方法，类似我们在largest rectangle in histogram当中考虑的，因为我们在这里只有先递减后递增才可以存水，所以我们维护一个递减栈来记录左边界，遇见比peek大的就弹出来算存水量，代码如下：

	class Solution {
	public:
	int trap(vector<int>& height) {
	int len = height.size(), vol = 0;
	stack<int> st;
	for(int i = 0; i < len; ++i)
	{
	int curr = height[i];
	while(st.size() && height[st.top()] < curr)
	{
	int top = height[st.top()];
	while(st.size() && height[st.top()] == top)
	st.pop();
	int width = st.empty()? i : i - st.top() - 1;
	if(st.size())
	vol += width * (min(curr, height[st.top()]) - top);
	}
	st.push(i);
	}
	return vol;
	}
	};

view raw trapping rain water_1.cpp hosted with ❤ by GitHub

值得注意的有几点，首先我们算存水面积不是按一个单位长度来算的，而是弹出的时候一层一层算的，弹出之后，peek就是左边界，要插入的是右边界，根据这些信息来算这一层。时间复杂度O(n)，空间复杂度O(n)。