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

rainwatertrap

 思路: 两指针方法,我们可以用两个指针,一个从左边往右边遍历,另一个从右边往左边遍历。先找到左右两边的第一个峰值作为参照位, 当从左往右遍历的时候,如果左指针找到的值比左边峰值小,就表示可以盛水,取他们的差值放到结果。 从右往左遍历的时候,如果右指针找到的值比右边峰值小,就把他们的差值放到结果。 难点在于,当两个峰值临近的时候,我们要取那个比较小的峰值来计算结果,因为积水区间是按较小的计算,所以我们在左右指针遍历之前要判断哪个比较小,就算哪个。

public class Solution {
    public int trap(int[] height) {
        if (height.length < 3 || height == null) 
            return 0;
        int sum = 0;
        int left = 0, right = height.length - 1;
        while(left < right && height[left] < height[left + 1]) left++; // find the first peek from left side
        while(left < right && height[right] < height[right - 1]) right--; // find the first peek from right side
        while(left < right) {
            int leftPeekVal = height[left];
            int rightPeekVal = height[right];
            //如果左边峰值较小,先计算左边
            if (leftPeekVal < rightPeekVal) {
                while(left < right && height[++left] < leftPeekVal) {
                    sum += leftPeekVal - height[left];
                }
            } else {
                while(left < right && height[--right] < rightPeekVal) {
                    sum += rightPeekVal - height[right];
                }

            }
        }
        return sum;

    }
}
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