一、题目给定n个非负整数表示每个宽度为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 个单位的雨水蓝色部分表示雨水。二、解法解法1双指针思路对于每个位置能接的水量 min(左边最大高度, 右边最大高度) - height[i]。我们不需要预先计算每个位置的左右最大值而是用两个指针从两端向中间移动同时维护左侧最大值leftMax和右侧最大值rightMax。如果height[left] height[right]说明左侧的短板决定了当前左侧位置的水量更新leftMax并计算left处的水量然后left。否则处理右侧。代码实现/** * param {number[]} height * return {number} */ var trap function(height) { if (height.length 3) return 0; let left 0, right height.length - 1; let leftMax 0, rightMax 0; let water 0; while (left right) { if (height[left] height[right]) { // 左边较低处理左指针 if (height[left] leftMax) { leftMax height[left]; } else { water leftMax - height[left]; } left; } else { // 右边较低或相等处理右指针 if (height[right] rightMax) { rightMax height[right]; } else { water rightMax - height[right]; } right--; } } return water; };解法2动态规划思路预先计算每个位置左侧最大值和右侧最大值然后遍历累加。代码实现/** * param {number[]} height * return {number} */ var trap function(height) { const n height.length; if (n 3) return 0; const leftMax new Array(n); const rightMax new Array(n); leftMax[0] height[0]; for (let i 1; i n; i) { leftMax[i] Math.max(leftMax[i-1], height[i]); } rightMax[n-1] height[n-1]; for (let i n-2; i 0; i--) { rightMax[i] Math.max(rightMax[i1], height[i]); } let water 0; for (let i 0; i n; i) { water Math.min(leftMax[i], rightMax[i]) - height[i]; } return water; };解法3单调栈思路维护一个递减栈遇到比栈顶高的柱子时弹出栈顶并计算积水。代码实现/** * param {number[]} height * return {number} */ var trap function(height) { const stack []; let water 0; for (let i 0; i height.length; i) { while (stack.length height[i] height[stack[stack.length - 1]]) { const top stack.pop(); if (!stack.length) break; const distance i - stack[stack.length - 1] - 1; const boundedHeight Math.min(height[i], height[stack[stack.length - 1]]) - height[top]; water distance * boundedHeight; } stack.push(i); } return water; };三、其他三种算法时间复杂度都是O(n).这道题是困难难度我也只大概理解了第一种算法逻辑还有些模糊可以慢慢理解。
