文章目录42.接雨水题目思路方法一动态规划思路步骤1定义两个辅助数组步骤2填充left_max数组从左到右遍历步骤3填充right_max数组从右到左遍历步骤4计算总接水量举例代码实现Go方法二双指针最优解空间O(1)思路步骤代码实现Go举例42.接雨水题目给定 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提示n height.length1 n 2 * 10^40 height[i] 10^5思路一个位置能接多少水取决于它「左边最高的柱子」和「右边最高的柱子」中更矮的那个减去当前柱子的高度。公式当前位置接水量 max(0, min(左最高, 右最高) - 当前高度)如果结果为负说明接不了水取 0方法一动态规划思路步骤1定义两个辅助数组left_max[i]表示「位置i左边不包含i的最高柱子高度」right_max[i]表示「位置i右边不包含i的最高柱子高度」。步骤2填充left_max数组从左到右遍历第一个位置i0左边没有柱子所以left_max[0] 0对于i0left_max[i] max(left_max[i-1], height[i-1])→ 解释位置i的左最高 「位置i-1的左最高」和「位置i-1的柱子高度」中更大的那个。步骤3填充right_max数组从右到左遍历最后一个位置in-1右边没有柱子所以right_max[n-1] 0对于in-1right_max[i] max(right_max[i1], height[i1])→ 解释位置i的右最高 「位置i1的右最高」和「位置i1的柱子高度」中更大的那个。步骤4计算总接水量遍历每个位置i用核心公式计算该位置接水量累加所有结果。举例示例1height [0,1,0,2,1,0,1,3,2,1,2,1]第一步算left_max数组i01234567891011height[i]010210132121left_max[i]001122223333i1left_max[1] max(left_max[0], height[0]) max(0,0)0i2left_max[2] max(left_max[1], height[1]) max(0,1)1i3left_max[3] max(left_max[2], height[2]) max(1,0)1以此类推…第二步算right_max数组i01234567891011height[i]010210132121right_max[i]333333322210i10right_max[10] max(right_max[11], height[11]) max(0,1)1i9right_max[9] max(right_max[10], height[10]) max(1,2)2以此类推…第三步计算每个位置接水量i01234567891011min(left_max, right_max)001122222210height[i]010210132121接水量001012100100累加接水量001012100100 6和示例1结果一致代码实现Gopackagemainimport(fmt)// trapDP 动态规划解法计算接雨水总量// 核心思路预处理每个位置的左最高和右最高高度再用核心公式计算每个位置接水量functrapDP(height[]int)int{n:len(height)ifn2{// 至少3个柱子才能接水否则直接返回0return0}// leftMax[i]位置i左侧不包含i的最高柱子高度leftMax:make([]int,n)leftMax[0]0// 第一个位置左侧无柱子最高高度为0fori:1;in;i{// 位置i的左最高 max(前一个位置的左最高, 前一个位置的柱子高度)leftMax[i]max(leftMax[i-1],height[i-1])}// rightMax[i]位置i右侧不包含i的最高柱子高度rightMax:make([]int,n)rightMax[n-1]0// 最后一个位置右侧无柱子最高高度为0fori:n-2;i0;i--{// 位置i的右最高 max(后一个位置的右最高, 后一个位置的柱子高度)rightMax[i]max(rightMax[i1],height[i1])}total:0// 总接水量fori:0;in;i{// 核心公式min(左最高, 右最高) - 当前高度结果0则取0current:min(leftMax[i],rightMax[i])-height[i]ifcurrent0{totalcurrent}}returntotal}// max 辅助函数返回两个整数的最大值// func max(a, b int) int {// if a b {// return a// }// return b// }// min 辅助函数返回两个整数的最小值// func min(a, b int) int {// if a b {// return a// }// return b// }funcmain(){// 示例1输入height1:[]int{0,1,0,2,1,0,1,3,2,1,2,1}// 示例2输入height2:[]int{4,2,0,3,2,5}// 输出结果fmt.Println(示例1输出动态规划,trapDP(height1))// 6fmt.Println(示例2输出动态规划,trapDP(height2))// 9}时间复杂度O (n)其中 n 是柱子数量。需要 3 次遍历数组填充 leftMax、填充 rightMax、计算总接水量每次遍历都是 O (n)。空间复杂度O (n)需要额外开辟两个长度为 n 的数组 leftMax 和 rightMax。方法二双指针最优解空间O(1)双指针是动态规划的空间优化版——不需要提前存储left_max和right_max数组而是用两个指针两个变量边遍历边计算。思路动态规划需要两个数组存所有位置的左/右最高但其实我们只需要「当前遍历位置的左最高和右最高」不需要存全部。关键观察对于位置left如果height[left] height[right]→ 该位置的接水量由左最高决定因为右边有更高的柱子左最高是短板对于位置right如果height[right] height[left]→ 该位置的接水量由右最高决定因为左边有更高的柱子右最高是短板。步骤初始化left左指针从0开始right右指针从n-1开始left_max记录左指针遍历过的位置的最高高度初始0right_max记录右指针遍历过的位置的最高高度初始0total总接水量初始0。循环left right如果height[left] height[right]→ 若height[left] left_max更新left_max为height[left]当前柱子更高接不了水→ 否则接水量 left_max - height[left]当前柱子比左最高矮能接水→ left指针右移否则height[left] height[right]→ 若height[right] right_max更新right_max为height[right]当前柱子更高接不了水→ 否则接水量 right_max - height[right]当前柱子比右最高矮能接水→ right指针左移。代码实现Gopackagemainimport(fmt)// trapTwoPointer 双指针解法计算接雨水总量// 核心思路用左右指针代替数组边遍历边计算左/右最高高度优化空间复杂度functrapTwoPointer(height[]int)int{n:len(height)ifn2{// 至少3个柱子才能接水return0}left:0// 左指针初始指向第一个柱子right:n-1// 右指针初始指向最后一个柱子leftMax:0// 左指针遍历过的区域的最高柱子高度rightMax:0// 右指针遍历过的区域的最高柱子高度total:0// 总接水量// 左右指针相遇时停止遍历forleftright{ifheight[left]height[right]{// 左边柱子更矮接水量由左最高决定ifheight[left]leftMax{leftMaxheight[left]// 更新左最高当前柱子更高无法接水}else{// 当前柱子比左最高矮能接的水量左最高-当前柱子高度totalleftMax-height[left]}left// 左指针右移}else{// 右边柱子更矮/相等接水量由右最高决定ifheight[right]rightMax{rightMaxheight[right]// 更新右最高当前柱子更高无法接水}else{// 当前柱子比右最高矮能接的水量右最高-当前柱子高度totalrightMax-height[right]}right--// 右指针左移}}returntotal}funcmain(){// 示例1输入height1:[]int{0,1,0,2,1,0,1,3,2,1,2,1}// 示例2输入height2:[]int{4,2,0,3,2,5}// 输出结果fmt.Println(示例1输出双指针,trapTwoPointer(height1))// 6fmt.Println(示例2输出双指针,trapTwoPointer(height2))// 9}时间复杂度O (n)仅需一次遍历数组每个柱子最多被访问一次。空间复杂度O (1)仅使用常数个变量left、right、leftMax、rightMax、total无额外数组开销。举例示例1height [0,1,0,2,1,0,1,3,2,1,2,1]初始化left0, right11, left_max0, right_max0, total0。步骤1height[left]0 height[right]1 → 处理leftheight[left]0 left_max0否 → 更新left_max0left → left1步骤2height[left]1 height[right]1否 → 处理rightheight[right]1 right_max0 → 更新right_max1right-- → right10步骤3height[left]1 height[right]2 → 处理leftheight[left]1 left_max0 → 更新left_max1left → left2步骤4height[left]0 height[right]2 → 处理leftheight[left]0 left_max1 → total 1-01total1left → left3步骤5height[left]2 height[right]2否 → 处理rightheight[right]2 right_max1 → 更新right_max2right-- → right9步骤6height[left]2 height[right]1否 → 处理rightheight[right]1 right_max2 → total 2-11total2right-- → right8步骤7height[left]2 height[right]2否 → 处理rightheight[right]2 right_max2 → 不更新right-- → right7步骤8height[left]2 height[right]3 → 处理leftheight[left]2 left_max1 → 更新left_max2left → left4步骤9height[left]1 height[right]3 → 处理leftheight[left]1 left_max2 → total 2-11total3left → left5步骤10height[left]0 height[right]3 → 处理leftheight[left]0 left_max2 → total 2-02total5left → left6步骤11height[left]1 height[right]3 → 处理leftheight[left]1 left_max2 → total 2-11total6left → left7此时left7 right7循环结束total6和示例1结果一致。