LeetCode: Trapping Rain Water

By | 2012 年 10 月 31 日

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.

Analyze

算法很简单,核心思想是:对某个值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),只扫了两遍。

Notes

  • 3.times{|i| p i}, prints 0,1,2

Solutions

Ruby

# @param {Integer[]} height
# @return {Integer}
def trap(height)
    # record the left heights
    lefts = []
    left = 0
    height.each do |h|
        lefts.push left
        left = h if left < h
    end
    # record the right heights
    rights = []
    right = 0
    height.size.times do |i|
        h = height[-i-1]
        rights.unshift(right)
        right = h if right < h
    end
    # calculate trapped
    trapped = 0
    lefts.each_with_index do |left, idx|
        right = rights[idx]
        h = height[idx]
        potential = [left, right].min - h
        trapped += potential if potential > 0
    end
    trapped
end

C++, 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

发表评论

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