首页 > 其他 > 详细

刷题64—接雨水

时间:2020-04-04 19:12:12      阅读:69      评论:0      收藏:0      [点我收藏+]

101.接雨水

题目链接

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/trapping-rain-water

题目描述

给定 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

重难点

每个元素的接水量相当于两边最大高度的较小值减去当前元素的高度。

题目分析

  1. 循环遍历元素。
  2. 每个元素的接水量相当于两边最大高度的较小值减去当前元素的高度。

 

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let total = 0;
    
    height.forEach((item,index)=>{
        let left = 0;
        let right = 0;
        for(let i=0;i<=index;i++){
            left = Math.max(height[i],left);
        }
        for(let j=index;j<height.length;j++){
            right = Math.max(height[j],right);
        }
        total += Math.min(left,right)-item;
    })
    return total;
};

  

刷题64—接雨水

原文:https://www.cnblogs.com/liu-xin1995/p/12632751.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!