LeetCode | Trapping Rain Water

题目

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!

从左到右遍历确定每个位置上左边的最高挡板，从右到左遍历确定每个位置上右边的最高挡板，然后就可以确定每个位置可以存多少水了（解法1）。

还可以参考Largest Rectangle in Histogram的思路，用栈保存所需信息，只用一次遍历即可得到结果（解法2）。

解法1

public class TrappingRainWater {
	public int trap(int[] A) {
		if (A == null || A.length == 0) {
			return 0;
		}
		int N = A.length;
		int[] leftHighest = new int[N];
		leftHighest[0] = A[0];
		for (int i = 1; i < N; ++i) {
			leftHighest[i] = Math.max(leftHighest[i - 1], A[i]);
		}

		int[] rightHighest = new int[N];
		rightHighest[N - 1] = A[N - 1];
		for (int i = N - 2; i >= 0; --i) {
			rightHighest[i] = Math.max(rightHighest[i + 1], A[i]);
		}

		int water = 0;
		for (int i = 0; i < N; ++i) {
			water += Math.min(leftHighest[i], rightHighest[i]) - A[i];
		}

		return water;
	}
}

解法2

public class TrappingRainWater {
	class Node {
		int val;
		int index;

		Node(int val, int index) {
			this.val = val;
			this.index = index;
		}
	}

	public int trap(int[] A) {
		if (A == null || A.length == 0) {
			return 0;
		}
		int water = 0;
		int N = A.length;
		Stack<Node> stack = new Stack<Node>();
		for (int i = 0; i < N; ++i) {
			if (stack.isEmpty()) {
				stack.push(new Node(A[i], i));
			} else {
				int height = 0;
				while (!stack.isEmpty()) {
					Node node = stack.peek();
					int width = i - node.index - 1;
					if (node.val > A[i]) {
						water += A[i] * width - height * width;
						stack.push(new Node(A[i], i));
						break;
					} else {
						water += node.val * width - height * width;
						height = node.val;
						stack.pop();
					}
				}
				if (stack.isEmpty()) {
					stack.push(new Node(A[i], i));
				}
			}
		}
		return water;
	}
}

LeetCode | Trapping Rain Water,,5-wow.com