【Trapping Rain Water】cpp

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

题目：

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!

代码：

class Solution {
public:
    int trap(vector<int>& height) {
            // non valid input
            int len = height.size();
            if (len<=2) return 0;
            // initial
            int left_max[height.size()];
            int right_max[height.size()];
            left_max[0] = 0;
            right_max[len-1] = 0;
            // get left_max and right_max
            for (int i = 1; i < len; ++i)
            {
                left_max[i] = std::max(left_max[i-1], height[i-1]);
                right_max[len-i-1] = std::max(right_max[len-i], height[len-i]);
            }
            // calculate the sum
            int sum = 0;
            for (int i = 0; i < len; ++i)
            {
                int h = std::min(left_max[i], right_max[i]);
                if (h>height[i])
                {
                    sum += h-height[i];
                }
            }
            return sum;
    }
};

Tips:

1. 遍历，获得每个位置上左边最高的和右边最高的；选择左边和右边比较小的高度，减去该位置的高度，就是可需水量。

2. 注意一些极端case的处理

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

标签： Android iOS 移动互联 终端开发

相关文章

随机文章

您可能还喜欢

您可能还喜欢