leecode 42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解法,左右对比实现累加

var trap = function(height) {
   let water = 0;
   if(height.length <=1) return 0;
   let largeL = 0;
   let largeR = 0;
   let left = 0;
   let right = height.length -1;
    while(left<right){
        largeL = Math.max(height[left],largeL);
        largeR = Math.max(height[right],largeR);
        if(largeL>largeR){
            water += largeR - height[right--]
        }else{
            water += largeL - height[left ++]
        }
    }
    return water
};
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 题目描述 给定n个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 上面是由...
    Roman_8e5f阅读 277评论 0 0
  • 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 上面是由数组 ...
    vbuer阅读 900评论 0 1
  • LeetCode 42 接雨水给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后...
    Phelthas阅读 522评论 0 0
  • 国家电网公司企业标准(Q/GDW)- 面向对象的用电信息数据交换协议 - 报批稿:20170802 前言: 排版 ...
    庭说阅读 11,133评论 6 13
  • 安卓的 【啰嗦几句题外话】如果项目添加了新插件,build ios之后,只需要替换www下面的文件即可 欢迎关注【...
    哎呦程序猿阅读 1,471评论 0 1