Trapping Rain Water

Leave a comment

October 31, 2016 by oneOokay

和这个极其相似:Largest rectangle in histogram

Largest rectangle in historgram 是在维护一个单调递增的栈,对于当前i需要找出i向左的第一个小于它的数和i向右的第一个小于它的数。

Trapping Rain Water则需要维护一个单调递减的栈,对于当前i需要找出i向左的第一个大于大的数和i向右的第一个大于它的数。(i为bottem).

初次写的代码如下:注意栈里面存的是index

public int trap(int[] height) {
if (height == null || height.length <= 2){
return 0;
}
Stack<Integer> stack = new Stack<Integer>();
int water = 0;
for (int i = 0; i < height.length; i ++) {
int current = height[i]; //这里并不需要push入一个Integer.MAX_VALUE,因为若是之后都是单调递减的话没有一个最大值,那么后面的那些就都盛不住水。不用考虑了。
while (!stack.isEmpty() && current > height[stack.peek()]){ //遇见了一个比peek大的值,需要进行pop操作
int right = i; //所以当前的值为peek()右边第一个比它大的数,所以当前的i为右边界
int bottom = stack.pop(); //peek()为bottom,凹处
if (stack.isEmpty()){ //这里注意因为左边界为pop完之后的一个数,如果没有的话就说明没有左边界,也盛不了水,直接break
break;
}
int left = stack.peek(); //找到左边界
water += (right – left – 1) * ( Math.min(height[left], height[right]) – height[bottom] );//水量:宽:右边界 – 左边界 – 1  ; 高:左右边界较小的一边 与 bottom的高度差。
}
stack.push(i);
}
return water;
}

 

稍微改进了一下的用一个while loop的解法:

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

Stack<Integer> stack = new Stack<Integer>();
int water = 0;
int i = 0;
while (i < height.length) {
if (stack.isEmpty() || height[i] <= height[stack.peek()]){
stack.push(i ++);
}else {
int bottom = stack.pop();
if (stack.isEmpty()){
continue;
}
water += (Math.min(height[stack.peek()], height[i]) – height[bottom]) * (i – stack.peek() -1);
}
}
return water;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: