[LeetCode] Trapping Rain Water

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!

 Solution:

基本思路是独立考虑每一个单位能容下的谁。比如上例中,坐标x~[2, 3]能装1个单位的水,[5, 6]能装2个单位的水,而能装的水的体积与该位置向左最高值LeftHighest,和向右最高值RightHighest相关。volume = max(0, min(LeftHighest, RightHighest)),有了这个认识,体积就很容易算出了。

 
class Solution {
public:
    int *leftHigh, *rightHigh;
    
    int trap(int A[], int n) {
        if(n < 3) return 0;
        
        int volume = 0;
        leftHigh = new int[n], rightHigh = new int[n];
        
        int left = 0, right = 0;
        for(int i = 0;i < n;i++)
        {
            leftHigh[i] = left;
            if(A[i] > left) left = A[i];
            rightHigh[n - 1 - i] = right;
            if(A[n - 1 - i] > right) right = A[n - 1 - i];
        }
        for(int i = 0;i < n;i++)
            volume += max(0, min(leftHigh[i], rightHigh[i]) - A[i]);
        
        return volume;
    }
};

[LeetCode] Trapping Rain Water,,5-wow.com

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