/*** @param {number[]} height* @return {number}*/
var trap = function (height) {let len = height.length;let pre_max = new Array(len).fill(0);let suf_max = new Array(len).fill(0);pre_max[0] = height[0];suf_max[len - 1] = height[len - 1];for (let i = 1; i < len; i++) {pre_max[i] = Math.max(pre_max[i - 1], height[i]);}for (let j = len - 2; j >= 0; j--) {suf_max[j] = Math.max(suf_max[j + 1], height[j]);}let ans = 0;for(let k = 0;k<len;k++){let h = height[k];let pre = pre_max[k]let suf = suf_max[k];ans +=(Math.min(pre,suf)-h)}return ans;
};console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1]))
console.log(trap([4,2,0,3,2,5]))

執行用時分布
63ms
擊敗69.22%使用 JavaScript 的用戶消耗內存分布
54.13MB
擊敗15.49%使用 JavaScript 的用戶

class Solution:def trap (self, height: List[int])->int:n = len(height)pre_max = [0]*npre_max[0] = height[0]suf_max = [0]*nsuf_max[-1] = height[-1]for i in range(1,n):pre_max[i]=max(pre_max[i-1],height[i])for i in range(len-2,-1,-1):suf_max[i] = max(suf_max[i+1],height[i])ans = 0for h,pre,suf in zip(height,pre_max,suf_max):ans+=min(pre,suf)-hreturn ans

• 優化空間復雜度O(1)

/*** @param {number[]} height* @return {number}*/
var trap = function(height) {let len = height.length;let left = 0,right = len-1;let pre_max = 0,suf_max = 0;let ans = 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;
};

執行用時分布
46ms 擊敗99.34%
使用 JavaScript 的用戶消耗內存分布
49.84MB擊敗98.37%
使用 JavaScript 的用戶