网站建设要费用多少,asp网站怎么做301,做视频网站都需要什么软件下载,高端网站建设 引擎技题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。
示例 1#xff1a; 输入#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出#xff1a;6 解释#xff1a;上面是由数组 [0,1,0,2,1,0,1,3…题目描述
给定 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 area0;let leftMax0;let rightMax0;for(let i0;iheight.length;i){rightMaxfindRightMax(leftMax,i,height);if(height[i]leftMaxrightMaxheight[i]){areaMath.min(leftMax,rightMax)-height[i];}else if(!findRightMax(leftMax,i,height)){leftMaxheight[i];}if(height[i]leftMax) leftMaxheight[i];}return area;
};
function findRightMax(num,j,height){let n0;for(let ij;iheight.length;i){if(height[i]num){return height[i];}if(height[i]n)nheight[i]}return n;
}执行结果 解法2双指针解法【注意理解】
/*** param {number[]} height* return {number}*/
var trap function(height) {let area0;if(height.length1) return 0;let left0;let leftMax0;let rightheight.length-1;let rightMax0;while(leftright){leftMaxMath.max(leftMax,height[left]);rightMaxMath.max(rightMax,height[right]);if(height[left]height[right]){arealeftMax-height[left];left;}else{arearightMax-height[right];right--;}}return area;
};
执行情况 解法3单调栈【参照力扣官方】
/*** param {number[]} height* return {number}*/
var trap function(height) {let area0;if(height.length1) return 0;const stack[]//存值值单调递减的下标for(let i0;iheight.length;i){while(stack.lengthheight[i]height[stack[stack.length-1]]){let topstack.pop();if(stack.length0){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;
};
