题目
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; } }