力扣热门100题之接雨水【困难】

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

解法1 按列计算

/*** @param {number[]} height* @return {number}*/
var trap = function(height) {let area=0;let leftMax=0;let rightMax=0;for(let i=0;i<height.length;i++){rightMax=findRightMax(leftMax,i,height);if(height[i]<leftMax&&rightMax>height[i]){area+=Math.min(leftMax,rightMax)-height[i];}else if(!findRightMax(leftMax,i,height)){leftMax=height[i];}if(height[i]>leftMax) leftMax=height[i];}return area;
};
function findRightMax(num,j,height){let n=0;for(let i=j;i<height.length;i++){if(height[i]>=num){return height[i];}if(height[i]>n)n=height[i]}return n;
}

执行结果：

解法2：双指针解法【注意理解】

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

执行情况：

解法3：单调栈【参照力扣官方】

/*** @param {number[]} height* @return {number}*/
var trap = function(height) {let area=0;if(height.length<=1) return 0;const stack=[]//存值值单调递减的下标for(let i=0;i<height.length;i++){while(stack.length&&height[i]>height[stack[stack.length-1]]){let top=stack.pop();if(stack.length==0){break;}const left = stack[stack.length - 1];const currWidth = i - left - 1;const currHeight = Math.min(height[left], height[i]) - height[top];area += currWidth * currHeight;}stack.push(i);}return area;
};