[leetcode] Trapping Rain Water

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

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.

技术分享

思路：

不会做，详细分析和思路参考此文。看懂了别人的，照葫芦画瓢弄了一个。

题解：

技术分享 
class Solution {
public:
    int trap(int A[], int n) {
        int res = 0;
        int maxIndex = 0;
        for(int i=1;i<n;i++)
            if(A[i]>A[maxIndex])
                maxIndex = i;
        int maxCur = A[0];
        for(int i=1;i<maxIndex;i++) {
            if(A[i]<maxCur)
                res += maxCur-A[i];
            else
                maxCur = A[i];
        }
        maxCur = A[n-1];
        for(int i=n-2;i>maxIndex;i--) {
            if(A[i]<maxCur)
                res += maxCur-A[i];
            else
                maxCur = A[i];
        }
        return res;
    }
};
View Code

 

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

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

相关文章

随机文章

您可能还喜欢

您可能还喜欢