LeetCode题目:Trapping Rain Water

By | 2012 年 10 月 31 日

算法很简单,核心思想是:对某个值A[i]来说,能trapped的最多的water取决于在i之前最高的值leftMostHeight[i]和在i右边的最高的值rightMostHeight[i]。(均不包含自身)。如果min(left,right) > A[i],那么在i这个位置上能trapped的water就是min(left,right) – A[i]。

有了这个想法就好办了,第一遍从左到右计算数组leftMostHeight,第二遍从右到左计算rightMostHeight,在第二遍的同时就可以计算出i位置的结果了,而且并不需要开空间来存放rightMostHeight数组。

时间复杂度是O(n),只扫了两遍。



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



代码,44ms过大集合

class Solution {
public:
    int trap(int A[], int n) {
        //no way to contain any water
        if(n <= 2) return 0;
        
        //1. first run to calculate the heiest bar on the left of each bar
        int *lmh = new int[n];//for the most height on the left
        lmh[0] = 0;
        int maxh = A[0];
        for(int i = 1; i < n; ++i) {
            lmh[i] = maxh;
            if(maxh < A[i]) maxh = A[i];
        }
        int trapped = 0;
        
        //2. second run from right to left, 
        // caculate the highest bar on the right of each bar
        // and calculate the trapped water simutaniously
        maxh = A[n-1];
        for(int i = n - 2; i > 0; --i) {
            int left = lmh[i];
            int right = maxh;
            int container = min(left,right);
            if(container > A[i]) {
                trapped += container - A[i];
            }
            if(maxh < A[i]) maxh = A[i];
        }
        delete lmh;
        return trapped;
    }
};

3 thoughts on “LeetCode题目:Trapping Rain Water

  1. Hong Jiang

    var Q = [0,1,0,2,1,0,0,1,3,2,1,2,1];

    function Trapping(Q) {
    var i = 0;
    var j = Q.length-1;
    var water = 0;

    while (i<j) {
    if (Q[i] Q[i+1]) {
    water = water + (Q[i]-Q[i+1]);
    Q[i+1] = Q[i];
    }
    i++;
    } else {
    if (Q[j-1] < Q[j]) {
    water = water + (Q[j]-Q[j-1]);
    Q[j-1] = Q[j];
    }
    j–;
    }
    }

    console.log(water);
    }

    Trapping(Q);

    Reply
  2. Pingback: [LeetCode] Trapping Rain Water - LifeXplorer

  3. 12344

    class Solution {
    public:
    int trap(int A[], int n) {
    if(n==0) return 0;
    int l = 0, r = n-1,block = 0,all = 0,curlevel = 0;
    while(lcurlevel)
    {
    all += (min(A[l],A[r])-curlevel)*(r-l+1);
    curlevel = min(A[l],A[r]);
    }
    if(A[l]<A[r])
    block += A[l++];
    else
    block += A[r–];
    }
    return all-block;
    }
    };

    Reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注