Trapping Rain Water, Leetcode 解题笔记

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

这题太坑爹了,一开始没想到好方法,观察规律,从左往右遍历每个坐标,如果比左边高,则继续遍历,如果比左边低,则开始记录,找右边第一个比当前高度高的,然后取左右两边中小的为宽,以左右两边距离为长,再减去两边之间所有的障碍物,然后把此值加入sum。结果实现中遇到各种边界问题和特殊情况,debug了半天没能通过。于是看别人答案,发现最优解法竟如此巧妙,这题分明就是一道数学题!

对于任何一个坐标,检查其左右的最大坐标,然后相减就是容积。所以,
1. 从左往右扫描一遍,对于每一个坐标,求取左边最大值。
2. 从右往左扫描一遍,对于每一个坐标,求最大右值。
3. 再扫描一遍,求取容积并加和。

public class Solution {
    public int trap(int[] A) {
        if(A.length < 3) return 0;
        int max = A[0];
        int[] left = new int[A.length];
        int[] right = new int[A.length];
        int sum = 0;
        
        for(int i = 1; i < A.length-1; i++){
            left[i] = max;
            if(A[i] > max){
                max = A[i];
            }
        }
        max = A[A.length-1];
        for(int i = A.length-2; i >=1; i--){
            right[i] = max;
            if(A[i] > max){
                max = A[i];
            }
        }
        for(int i = 1; i < A.length-1; i++){
            int cur = Math.min(left[i], right[i]) - A[i];
            if(cur > 0){
                sum += cur;
            }
        }
        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