# 算法练习Stack(三)--P42

link on JianShu

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. 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!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6

Hard模式果然不同凡响啊，这是什么鬼。完全没有思路好嘛。只能先去看看别人是怎么搞出来的了。

public int trap(int[] height) {
if (height == null || height.length < 2) return 0;

Stack<Integer> stack = new Stack<>();
int water = 0, i = 0;
while (i < height.length) {
if (stack.isEmpty() || height[i] <= height[stack.peek()]) {
stack.push(i++);
} else {
int pre = stack.pop();
if (!stack.isEmpty()) {
// find the smaller height between the two sides
int minHeight = Math.min(height[stack.peek()], height[i]);
// calculate the area
water += (minHeight - height[pre]) * (i - stack.peek() - 1);
}
}
}
return water;
}


comments powered by Disqus