LeetCode42.接雨水 JavaScript

BearyChat 發布于2019-08-23 15:43 / 724人閱讀

摘要：給定個非負整數表示每個寬度為的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。上面是由數組表示的高度圖，在這種情況下，可以接個單位的雨水藍色部分表示雨水。示例輸入輸出答案參考

給定 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機柜

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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