[LintCode 363] 接雨水(Python)

题目描述

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.
样例
如上图所示，海拔分别为 [0,1,0,2,1,0,1,3,2,1,2,1], 返回 6.

思路

观察图片可知，接满雨水后，总体呈现先增后降的趋势。所以先遍历一遍，找到峰值的下标。再从两头向峰值遍历，不符合递增趋势的数值，都是需要计算填充差值的。

代码

class Solution:
    """
    @param: heights: a list of integers
    @return: a integer
    """
    def trapRainWater(self, heights):
        # write your code here
        if heights is None or len(heights) <= 2:
            return 0
        max_id = 0
        for i in range(1, len(heights)):
            if heights[i] > heights[max_id]:
                max_id = i

        res = 0
        s = 0
        cur = heights[s]
        while s < max_id:
            if heights[s] >= cur:
                cur = heights[s]
            else:
                res += 1 * (cur - heights[s])
            s += 1

        e = len(heights) - 1
        cur = heights[e]
        while e > max_id:
            if heights[e] >= cur:
                cur = heights[e]
            else:
                res += 1 * (cur - heights[e])
            e -= 1
        return res

复杂度分析

时间复杂度

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/yurenguowang/article/details/78043776
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2020-06-27 23:27:59
阅读 ( 667 )
分类：

[LintCode 363] 接雨水(Python)

题目描述

思路

代码

复杂度分析

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看