LeetCode 热题 100 —— 7.接雨水（Javascript解法）-尧图网络科技

一、题目

给定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[i+1], 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; };