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 MarcZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcyBmb3IgY29udHJpYnV0aW5nIHRoaXMgaW1hZ2UhPC9wPgo8c3Ryb25nPrfWzvY8L3N0cm9uZz4KPHA+tNPX87W909Kx6cD6yLe2qMO/uPbOu9bDyc/X87HftcTX7rjftbKw5aOstNPT0rW91/Ox6cD6yLe2qMO/uPbOu9bDyc/T0rHftcTX7rjftbKw5aOsyLu6877Nv8nS1Mi3tqjDv7j2zrvWw7/J0tS05rbgydnLrsHLo6i94reoMaOpoaM8L3A+CjxwPru5v8nS1LLOv7xMYXJnZXN0IFJlY3RhbmdsZSBpbiBIaXN0b2dyYW21xMu8wrejrNPD1buxo7Tmy/nQ6NDFz6KjrNa708PSu7TOsenA+ry0v8m1w7W9veG5+6OoveK3qDKjqaGjPC9wPgo8cD48c3Ryb25nPr3it6gxPC9zdHJvbmc+PC9wPgo8cD48L3A+CjxwcmUgY2xhc3M9"brush:java;">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 stack = new Stack();
		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;
	}
}