題目
給定?n 個非負整數表示每個寬度為 1 的柱子的高度圖,計算按此排列的柱子,下雨之后能接多少雨水。
解析
和題目 盛水最多的容器 類似,
LeetCode Hot 100:11. 盛最多水的容器-CSDN博客
只是這里將每一個柱子視為一個寬度為1的容器,能接水的體積取決于左邊最大高度和右邊最大高度的較小值,再減去底部當前柱子的高度。設置左右指針left和right,指向左右兩側當前待計算接水量的柱子,以及記錄左指針以左、右指針以右的最大高度值的pre_max和suf_max兩個變量。
作者:靈茶山艾府
來源:
盛最多水的容器 接雨水【基礎算法精講 02】_嗶哩嗶哩_bilibili
答案
注意while循環可以不加等號,因為在「誰小移動誰」的規則下,相遇的位置一定是最高的柱子,這個柱子是無法接水的。
作者:靈茶山艾府
來源:42. 接雨水 - 力扣(LeetCode)
/*** @param {number[]} height* @return {number}*/
var trap = function(height) {const len = height.length;let left = 0, right = len - 1, ans = 0; //設置左右指針和初始答案//初始化前綴最大高度(左指針以左),后綴最大高度(右指針以右)let pre_max = 0, suf_max = 0;while(left < right) {pre_max = Math.max(pre_max, height[left]); //更新前綴最大高度suf_max = Math.max(suf_max, height[right]); //更新后綴最大高度 if(pre_max < suf_max) { //判斷儲水高度,取決于前綴、后綴最大高度中的短邊ans += pre_max - height[left]; //實際可儲水高度需要減去底部柱子的高度left++;} else {ans += suf_max - height[right];right--;}}return ans;
};
復雜度分析
時間復雜度:O(n),其中?n?為?height?的長度。
空間復雜度:O(1),僅用到若干額外變量。