LeetCode42.接雨水 JavaScript

BearyChat 发布于2019-08-23 15:43 / 723人阅读

摘要：给定个非负整数表示每个宽度为的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。上面是由数组表示的高度图，在这种情况下，可以接个单位的雨水蓝色部分表示雨水。示例输入输出答案参考

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

答案参考：

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    let left = 0, right = height.length - 1
    let count = 0
    let leftMax = 0, rightMax = 0
    while (left <= right) {
        leftMax = Math.max(leftMax, height[left])
        rightMax = Math.max(rightMax, height[right])
        if (leftMax < rightMax) {
            count += leftMax - height[left]
            left++
        } else {
            count += rightMax - height[right]
            right--
        }
    }
    return count
};

云服务器 GPU云服务器 LeetCode LeetCode_String leetcode_35_SearchIn 42u机柜

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/102496.html

LeetCode.42 接雨水(Trapping Rain Water)(JS)

摘要：一题目接雨水给定个非负整数表示每个宽度为的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。上面是由数组表示的高度图，在这种情况下，可以接个单位的雨水蓝色部分表示雨水。提交，答案错误。出错的测试用例为。做有意思的题是要付出代价的，代价就是死活做不出来。一、题目接雨水：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。show...

MartinDai 2019-08-23 18:05 评论0 收藏0
6-9月技术文章汇总

摘要：分布式的管理和当我在谈论架构时我在谈啥状态码详解无状态协议和请求支持哪些方法分层协议栈有哪些数据结构运用场景说说你常用的命令为什么要有包装类面向对象的特征是啥是啥有什么好处系统设计工程在线诊断系统设计与实现索引背后的数据结构及算法原理软技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】当我在谈论RestFul架构时我在谈啥？...

miya 2019-07-30 18:03 评论0 收藏0
LeetCode.11 盛最多水的容器(Container With Most Water)(JS

摘要：一题目盛最多水的容器给定个非负整数，，，，每个数代表坐标中的一个点。在坐标内画条垂直线，垂直线的两个端点分别为和。找出其中的两条线，使得它们与轴共同构成的容器可以容纳最多的水。在此情况下，容器能够容纳水表示为蓝色部分的最大值为。一、题目盛最多水的容器：给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i ...

muddyway 2019-08-26 10:12 评论0 收藏0
[LintCode/LeetCode] Trapping Rain Water [栈和双指针]

摘要：一种是利用去找同一层的两个边，不断累加寄存。双指针法的思想先找到左右两边的第一个峰值作为参照位，然后分别向后向前每一步增加该位与参照位在这一位的差值，加入，直到下一个峰值，再更新为新的参照位。 Problem Given n non-negative integers representing an elevation map where the width of each bar i...

bluesky 2019-08-14 15:19 评论0 收藏0
《面向前端的leetcode题解》

《面向前端的leetcode题解》最近更新了《盛雨水问题》，《吃香蕉问题》，求关注，求star showImg(https://segmentfault.com/img/bVbrfwG?w=1123&h=630);showImg(https://segmentfault.com/img/bVbrfwE?w=1017&h=552);showImg(https://segmentfault.co...

Pink 2019-08-23 16:53 评论0 收藏0