Leetcode: Trapping Rain Water

浏览数：16 / 时间：2015年06月11日

Problem:

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.

技术分享

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

Code:

public class Solution {
    public int trap(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        int[] leftMost = new int[A.length];
        int[] rightMost = new int[A.length];
        leftMost[0] = A[0];
        rightMost[A.length - 1] = A[A.length - 1];
        for (int i = 1; i < A.length; i++) {
            leftMost[i] = Math.max(leftMost[i - 1], A[i]);
        }
        for (int i = A.length - 2; i >= 0; i--) {
            rightMost[i] = Math.max(rightMost[i + 1], A[i]);
        }
        int sum = 0;
        for (int i = 1; i < A.length - 1; i ++) {
            sum = sum + (Math.min(rightMost[i], leftMost[i]) - A[i]);
        }
        return sum;
    }
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

Leetcode: Trapping Rain Water