Lexi's Leetcode solutions

[leetcode] Trapping Rain Water | 俄罗斯方块一样的一排能接多少雨水

Posted on: October 3, 2013

这题不好想,还是看了答案才明白。中心思路是:每个bar头顶能接多少水,取决于它两边有木有比自己高的两个木板,有的话自己上方就被trap住了,trap的volumn是(两边比自己高的那两个模板中的短板-自己的高度)×1。
然后就要考虑怎么求在每个木板i,他的左边最高板和右边最高板的值呢?用dp一试就出来了。这个就是因为很熟练LIS了,所以一下就做出来了。这种接水题也是,现在觉得难,多做几道思路就清晰了吧。

public int trap(int[] A) {
    int[] left = new int[A.length];
    int[] right = new int[A.length];
    for (int i = 0; i < A.length; i++) {
        left[i] = i > 0 ? Math.max(left[i - 1], A[i]) : A[i];
    }
    for (int i = A.length - 1; i >= 0; i--) {
        right[i] = i < A.length - 1 ? Math.max(right[i + 1], A[i]) : A[i];
    }
    int res = 0;
    for (int i = 1; i < A.length - 1; i++) { //two edges can't trap nothin'
        int lowBar = Math.min(left[i - 1], right[i + 1]);
        if (lowBar > A[i])
            res += lowBar - A[i];
    }
    return res;
}

2 Responses to "[leetcode] Trapping Rain Water | 俄罗斯方块一样的一排能接多少雨水"

解法很清晰。 可否解释下是怎么用DP试的?谢谢

就前两个for循环,第一个算左边最高,第二个算的是右边最高。

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: