[Algorithm]Trapping Rain Water II

如果我们把0看做漏水，这个题目的解法该怎么变化呢。首先考虑我们Trapping Rain Water中考虑的第一种dp解法，我们要做变化的就是如果当前是0的话，我们把arr的值也设为0，并且，从左向右扫的时候，如果前一个是0并且当前是递增序列的话，也是没有办法存水的。从右向左扫的时候是类似的。DP方程如下：

• if A[i] == 0, f[i] = 0;
• else if A[i - 1] == 0 && A[i - 1] <= A[i], f[i] = 0;
• else, f[i] = max(f[i - 1], A[i - 1]);

对于第二种解法，没有太好的办法可以用过来，原因是在第一题当中第二种方法我们移动指针的时候可以确保可以存水的，但是当0代表漏水的时候，我们不能保证中间递减的一块还可以存水了，所以双指针方法不好运用过来。
第三种方法，我们可以当check到0的时候，把栈清空，然后坐标移到下一个递减序列的开头，这样就可以。代码如下：

	public class TrappingRainWater {
	public int trapI(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++) {
	if (A[i] == 0)
	left[i] = 0;
	else if (left[i - 1] == 0 && A[i - 1] <= A[i])
	left[i] = 0;
	else
	left[i] = A[i - 1] >= left[i - 1]? A[i - 1]: left[i - 1];
	}
	for (int i = len - 2; i >= 0; i--) {
	if (A[i] == 0)
	right = 0;
	else if (right == 0 && A[i] >= A[i + 1])
	right = 0;
	else
	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;
	}
	public int trapII(int[] A) {
	if (A == null)
	return 0;
	int len = A.length;
	if (len < 3)
	return 0;
	Stack<Integer> stack = new Stack<Integer>();
	int sum = 0;
	for (int i = 0; i < len;) {
	if (A[i] == 0) {
	while (!stack.isEmpty())
	stack.pop();
	while (i < len - 1 && A[i] <= A[i + 1])
	i++;
	if (i == len - 1)
	break;
	continue;
	} else {
	if (!stack.isEmpty() && A[stack.peek()] <= A[i]) {
	int base = A[stack.peek()];
	stack.pop();
	while (!stack.isEmpty() && A[stack.peek()] <= A[i]) {
	sum += (A[stack.peek()] - base) * (i - stack.peek() - 1);
	base = A[stack.pop()];
	}
	sum += stack.isEmpty()? 0: (A[i] - base) * (i - stack.peek() - 1);
	}
	stack.push(i++);
	}
	}
	return sum;
	}
	public static void main(String[] args) {
	test1();
	test2();
	test3();
	test4();
	test5();
	test6();
	test7();
	}
	//test cases
	public static void test1() {
	int[] A = {2,0,2};
	TrappingRainWater t = new TrappingRainWater();
	if (t.trapI(A) == 0 && t.trapII(A) == 0)
	System.out.println("Test case 1 passed!");
	else
	System.out.println("Test case 1 failed!");
	}
	public static void test2() {
	int[] A = {0,1,0,2,1,0,1,3,2,1,2,1};
	TrappingRainWater t = new TrappingRainWater();
	if (t.trapI(A) == 1 && t.trapII(A) == 1)
	System.out.println("Test case 2 passed!");
	else
	System.out.println("Test case 2 failed!");
	}
	public static void test3() {
	int[] A = {3,2,1,0,2,3,2,1,3,0,3};
	TrappingRainWater t = new TrappingRainWater();
	if (t.trapI(A) == 3 && t.trapII(A) == 3)
	System.out.println("Test case 3 passed!");
	else
	System.out.println("Test case 3 failed!");
	}
	public static void test4() {
	int[] A = {5,3,1,4,0,1,3,5,6,3,2,3,1};
	TrappingRainWater t = new TrappingRainWater();
	if (t.trapI(A) == 5 && t.trapII(A) == 5)
	System.out.println("Test case 4 passed!");
	else
	System.out.println("Test case 4 failed!");
	}
	public static void test5() {
	int[] A = {32,16,5,7,17,28,0,9,10,11,4,5,22,27,0,2,4,3,2,5};
	TrappingRainWater t = new TrappingRainWater();
	if (t.trapI(A) == 83 && t.trapII(A) == 83)
	System.out.println("Test case 5 passed!");
	else
	System.out.println("Test case 5 failed!");
	}
	public static void test6() {
	int[] A = {0,0,0,0,0,0,0,10,5,4,7,0,10,0,0,0};
	TrappingRainWater t = new TrappingRainWater();
	if (t.trapI(A) == 5 && t.trapII(A) == 5)
	System.out.println("Test case 6 passed!");
	else
	System.out.println("Test case 6 failed!");
	}
	public static void test7() {
	int[] A = {0,0,0,0,0,0,0,10,5,4,7,0,10,0,0,5};
	TrappingRainWater t = new TrappingRainWater();
	if (t.trapI(A) == 5 && t.trapII(A) == 5)
	System.out.println("Test case 7 passed!");
	else
	System.out.println("Test case 7 failed!");
	}
	}

view raw trapping rain water follow up.java hosted with ❤ by GitHub

注意如果给的array里最后有以连续的0结尾，第51行是为了避免程序出不去的情况发生，因为最后两个如果也是递减序列或者高度相同也是存不了水的。