42. Trapping Rain Water 接雨水【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go题目描述给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水。感谢 Marcos 贡献此图。题目大意从 x 轴开始给出一个数组数组里面的数字代表从 (0,0) 点开始宽度为 1 个单位高度为数组元素的值。如果下雨了问这样一个容器能装多少单位的水解题思路核心抽象每个位置的水量针对每个下标 i找到它左边最大值 leftMax右边的最大值 rightMax然后 min(leftMaxrightMax) 为能够接到水的高度。left 和 right 指针是两边往中间移动的游标指针。最傻的解题思路是针对每个下标 i往左循环找到第一个最大值往右循环找到第一个最大值然后把这两个最大值取出最小者即为当前雨水的高度。这样做时间复杂度高浪费了很多循环。i 在从左往右的过程中是可以动态维护最大值的。右边的最大值用右边的游标指针来维护。从左往右扫一遍下标和从两边往中间遍历一遍下标是相同的结果每个下标都遍历了一次。每个 i 的宽度固定为 1所以每个坑只需要求出高度即当前这个坑能积攒的雨水。最后依次将每个坑中的雨水相加即是能接到的雨水数。朴素解法双重循环动态规划解法预处理左右最大值双指针解法推荐每个数组里面的元素值可以想象成一个左右都有壁的圆柱筒。例如下图中左边的第二个元素 1当前左边最大的元素是 2 所以 2 高度的水会装到 1 的上面因为想象成了左右都有筒壁。这道题的思路就是左指针从 0 开始往右扫右指针从最右边开始往左扫。额外还需要 2 个变量分别记住左边最大的高度和右边最大高度。遍历扫数组元素的过程中如果左指针的高度比右指针的高度小就不断的移动左指针否则移动右指针。循环的终止条件就是左右指针碰上以后就结束。只要数组中元素的高度比保存的局部最大高度小就累加 res 的值否则更新局部最大高度。最终解就是 res 的值。单调栈解法补充代码仓库实现双指针O(n) / O(1)补充实现动态规划补充实现单调栈测试用例与运行验证复杂度对比小结在本仓库中的归类与延伸阅读LeetCode-Go 题解 42 | Trapping Rain Water 接雨水双指针与动态规划全解析导读本文围绕 LeetCode 第 42 题Trapping Rain Water接雨水展开完整讲解题目语义、三种主流通用解法双重循环、动态规划、双指针以及单调栈思路并逐行剖析当前仓库 LeetCode-Go 中leetcode/0042.Trapping-Rain-Water目录下的 Go 实现与测试用例。读完本文你不仅能理解每个位置能接多少水 min(左侧最高, 右侧最高) − 当前高度这一核心抽象还能掌握 O(n) 时间、O(1) 空间的经典双指针写法及其正确性直觉并可直接在本地运行仓库测试验证结果。题目描述给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。示例中的高度图由数组[0,1,0,2,1,0,1,3,2,1,2,1]表示柱子宽度为 1数组元素即柱高该地形可以接6 个单位的雨水即图中蓝色区域。示例Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6逐列拆解验证每个下标对应一根宽度为 1 的柱子可积水高度 min(左侧最高, 右侧最高) − 当前柱高取非负值下标高度左侧最高右侧最高可接雨水00030110302013132130412315023261231732208232091321102310111300合计恰好为 6与题目输出一致。题目大意从 x 轴开始给出一个数组数组里面的数字代表从 (0,0) 点开始宽度为 1 个单位高度为数组元素的值。如果下雨了问这样一个容器能装多少单位的水换一种更直观的理解方式把数组想象成一面从左到右起伏的城墙剖面柱与柱之间天然形成若干个坑。雨水会填满每个坑直到从该坑向左看和向右看都看不到更高的墙为止。题目要求的正是这些坑中雨水体积的总和。由于每个柱子的宽度固定为 1问题退化为求每个位置能积攒的雨水高度再求和。解题思路核心抽象每个位置的水量 min(左侧最高, 右侧最高) − 当前高度本题的关键抽象如下针对每个下标 i找到它左边最大值leftMax右边的最大值rightMax然后min(leftMax, rightMax)就是该位置能够接到水的高度上限实际可接水量 max(0, min(leftMax, rightMax) − height[i])每个 i 的宽度固定为 1所以每个坑只需要求出高度即当前这个坑能积攒的雨水。最后依次将每个坑中的雨水相加即是能接到的雨水数。基于这一抽象可以推导出由朴素到最优的多种解法。朴素解法双重循环O(n²) / O(1)最直接的思路是对每个下标 i往左循环找到左侧最大值往右循环找到右侧最大值取二者较小者减去当前高度累加到结果中。func trapBruteForce(height []int) int { res : 0 for i : 1; i len(height)-1; i { leftMax, rightMax : 0, 0 for j : i; j 0; j-- { // 向左找最大值 if height[j] leftMax { leftMax height[j] } } for j : i; j len(height); j { // 向右找最大值 if height[j] rightMax { rightMax height[j] } } if min : leftMax; rightMax min { min rightMax } if v : min - height[i]; v 0 { res v } } return res }这样做时间复杂度高浪费了很多循环——每个下标都要向左右各扫描一遍整体复杂度为 O(n²)。它虽然正确但只适合规模很小的输入。动态规划解法预处理左右最大值数组O(n) / O(n)i 在从左往右的过程中是可以动态维护最大值的。因此可以先用两趟线性扫描分别预计算leftMax[i]从 0 到 i 的区间最大值含 i 自身rightMax[i]从 i 到 n−1 的区间最大值含 i 自身。然后每个位置只需 O(1) 查表累加func trapDP(height []int) int { n : len(height) if n 0 { return 0 } leftMax : make([]int, n) rightMax : make([]int, n) leftMax[0] height[0] for i : 1; i n; i { if height[i] leftMax[i-1] { leftMax[i] height[i] } else { leftMax[i] leftMax[i-1] } } rightMax[n-1] height[n-1] for i : n - 2; i 0; i-- { if height[i] rightMax[i1] { rightMax[i] height[i] } else { rightMax[i] rightMax[i1] } } res : 0 for i : 0; i n; i { m : leftMax[i] if rightMax[i] m { m rightMax[i] } if v : m - height[i]; v 0 { res v } } return res }时间 O(n)、额外空间 O(n)。该解法与min(左侧最大值, 右侧最大值)的抽象一一对应是最直观、最容易写对的版本。双指针解法两侧向中间收缩O(n) / O(1)这是本仓库实际采用的解法也是面试中推荐的最优写法。核心思想左指针从 0 开始往右扫右指针从最右边开始往左扫额外需要 2 个变量分别记住左边最大的高度maxLeft和右边最大高度maxRight遍历扫数组元素的过程中如果左指针的高度比右指针的高度小就不断地移动左指针否则移动右指针循环的终止条件是左右指针碰上以后就结束只要数组中元素的高度比保存的局部最大高度小就累加res的值否则更新局部最大高度最终解就是res的值。正确性直觉当height[left] height[right]时右指针位置已经存在一根不低于当前左指针高度的墙作为兜底因此左指针当前位置的储水量只由左侧已扫描到的最大高度maxLeft决定左侧最高墙封顶反之当右指针高度更小时对称地处理右指针。这一过程与动态规划版本逐位置计算min(左侧最高, 右侧最高) − 当前高度完全等价只是通过哪边矮就先处理哪边的方式把两个长度为 n 的辅助数组压缩成了两个变量空间降到 O(1)。此外每个数组里面的元素值可以想象成一个左右都有壁的圆柱筒例如示例中下标 2 的元素 0其左侧最大元素是 1下标 1所以 1 高度的水会装到它的上面因为想象成了左右都有筒壁而下标 5 的元素 0左侧最大是 2下标 3、右侧最大是 3下标 7因此它能接到 2 高度的水。边界情况说明数组长度不足 3如空数组、单元素、两元素时必然接不到水严格递增或严格递减的地形中每个位置的高度都会不断刷新maxLeft/maxRightres恒为 0。这些情况在下面的双指针实现中都会被自然处理无需特判。单调栈解法补充思路除上述三种主流解法外本题还常用单调递减栈处理从左到右遍历维护一个高度单调递减的栈当遇到比栈顶更高的柱子时说明出现了坑的右壁此时弹出栈顶作为坑底取新的栈顶左侧壁与当前柱子右侧壁中较矮者作为水位高度乘以两壁之间的宽度累加面积。该解法时间复杂度 O(n)、空间复杂度 O(n)适合作为对比学习的补充仓库本题实现未采用此方案。仓库源码实现逐行解析本题的完整实现位于 leetcode/0042.Trapping-Rain-Water 目录下源文件为42. Trapping Rain Water.go全文如下package leetcode func trap(height []int) int { res, left, right, maxLeft, maxRight : 0, 0, len(height)-1, 0, 0 for left right { if height[left] height[right] { if height[left] maxLeft { maxLeft height[left] } else { res maxLeft - height[left] } left } else { if height[right] maxRight { maxRight height[right] } else { res maxRight - height[right] } right-- } } return res }逐行拆解对应源文件第 322 行第 4 行变量初始化res累计总雨水量初始为 0left指向最左下标 0right指向最右下标len(height)-1maxLeft、maxRight分别记录左右两侧已扫描到的最大高度初始为 0。第 5 行循环终止条件for left right左右指针碰上以后循环结束——这正是原文档中循环的终止条件就是左右指针碰上以后就结束的实现。注意这里用而不是可以保证在指针相遇的那个位置也被正确结算相遇时两侧高度相同走左分支用maxLeft结算该点。第 612 行左分支当height[left] height[right]时处理左指针。若当前高度刷新了maxLeft则说明当前柱子本身就是左侧新的最高墙此处不可能积水只更新maxLeft不累加否则当前位置是一处坑能接maxLeft - height[left]的水累加到res然后left向右推进。第 1319 行右分支对称处理右指针。当height[right] maxRight时更新右侧最高墙否则累加maxRight - height[right]然后right--向左推进。第 22 行循环结束返回res即接到的雨水总量。这里有一个值得注意的对称细节左分支的更新条件是height[left] maxLeft严格大于才更新右分支是height[right] maxRight大于等于即更新。由于两侧分支的进入条件是/互补的这种写法配合left right的循环条件保证指针相遇位置不会被重复或遗漏结算读者可自行用示例数组逐指针推演验证。测试用例与运行验证同目录下的测试文件42. Trapping Rain Water_test.go使用本仓库统一的问题-参数-答案结构question42/para42/ans42组织用例package leetcode import ( fmt testing ) type question42 struct { para42 ans42 } // para 是参数 // one 代表第一个参数 type para42 struct { one []int } // ans 是答案 // one 代表第一个答案 type ans42 struct { one int } func Test_Problem42(t *testing.T) { qs : []question42{ { para42{[]int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}}, ans42{6}, }, } fmt.Printf(------------------------Leetcode Problem 42------------------------\n) for _, q : range qs { _, p : q.ans42, q.para42 fmt.Printf(【input】:%v 【output】:%v\n, p, trap(p.one)) } fmt.Printf(\n\n\n) }测试用例与题目示例完全一致输入[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]期望输出 6。运行方式如下仓库go.mod声明模块为github.com/halfrost/LeetCode-GoGo 版本要求go 1.19且通过 replace 指令将structures、template、ctl/util、ctl/models指向本地子目录go test -v ./leetcode/0042.Trapping-Rain-Water/或在题目目录内直接运行cd leetcode/0042.Trapping-Rain-Water go test -v -run Test_Problem42 .测试通过时输出PASS并打印形如【input】:[0 1 0 2 1 0 1 3 2 1 2 1] 【output】:6的调试信息。读者也可以复制该测试文件自行追加更多用例如空数组、递增/递减数组、等高地形的边界场景来验证双指针实现的鲁棒性。复杂度对比小结解法时间复杂度空间复杂度说明双重循环朴素O(n²)O(1)每个下标向左右各扫描一次最易理解但效率低动态规划预计算左右最大值O(n)O(n)与核心抽象一一对应最直观的 O(n) 写法双指针本仓库实现O(n)O(1)两侧向中间收缩最优时间与空间面试推荐单调栈O(n)O(n)用遇高弹出模拟坑的结算适合对比学习双指针版本每个下标恰好被访问一次由left或right其中一侧结算因此时间复杂度严格为 O(n)且不依赖任何额外数组空间复杂度 O(1)。在本仓库中的归类与延伸阅读本题在本仓库的题解站点中位于 website/content/ChapterFour/0001~0099/0042.Trapping-Rain-Water.md含英文版 website/content.en/ChapterFour/0001~0099/0042.Trapping-Rain-Water.md同时被归入双指针、栈、数组、动态规划等多个专题页见 website/content/ChapterTwo/Two_Pointers.md 与 website/content/ChapterTwo/Stack.md。读者可在这些专题目录下找到大量采用相同套路相向双指针、单调栈的题目对照学习。延伸练习建议本题的变体与姊妹题在仓库中均有实现例如接雨水问题的相关进阶题如最大矩形、柱状图中的最大矩形等可结合专题页按图索骥而每个位置由两侧最高值决定的抽象也可迁移到双向扫描类问题的思考中。若想验证仓库整体测试可在仓库根目录执行go test ./...gotest.sh脚本亦提供了批量测试入口。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 42. Trapping Rain Water 接雨水
42. Trapping Rain Water 接雨水【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go题目描述给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水。感谢 Marcos 贡献此图。题目大意从 x 轴开始给出一个数组数组里面的数字代表从 (0,0) 点开始宽度为 1 个单位高度为数组元素的值。如果下雨了问这样一个容器能装多少单位的水解题思路核心抽象每个位置的水量针对每个下标 i找到它左边最大值 leftMax右边的最大值 rightMax然后 min(leftMaxrightMax) 为能够接到水的高度。left 和 right 指针是两边往中间移动的游标指针。最傻的解题思路是针对每个下标 i往左循环找到第一个最大值往右循环找到第一个最大值然后把这两个最大值取出最小者即为当前雨水的高度。这样做时间复杂度高浪费了很多循环。i 在从左往右的过程中是可以动态维护最大值的。右边的最大值用右边的游标指针来维护。从左往右扫一遍下标和从两边往中间遍历一遍下标是相同的结果每个下标都遍历了一次。每个 i 的宽度固定为 1所以每个坑只需要求出高度即当前这个坑能积攒的雨水。最后依次将每个坑中的雨水相加即是能接到的雨水数。朴素解法双重循环动态规划解法预处理左右最大值双指针解法推荐每个数组里面的元素值可以想象成一个左右都有壁的圆柱筒。例如下图中左边的第二个元素 1当前左边最大的元素是 2 所以 2 高度的水会装到 1 的上面因为想象成了左右都有筒壁。这道题的思路就是左指针从 0 开始往右扫右指针从最右边开始往左扫。额外还需要 2 个变量分别记住左边最大的高度和右边最大高度。遍历扫数组元素的过程中如果左指针的高度比右指针的高度小就不断的移动左指针否则移动右指针。循环的终止条件就是左右指针碰上以后就结束。只要数组中元素的高度比保存的局部最大高度小就累加 res 的值否则更新局部最大高度。最终解就是 res 的值。单调栈解法补充代码仓库实现双指针O(n) / O(1)补充实现动态规划补充实现单调栈测试用例与运行验证复杂度对比小结在本仓库中的归类与延伸阅读LeetCode-Go 题解 42 | Trapping Rain Water 接雨水双指针与动态规划全解析导读本文围绕 LeetCode 第 42 题Trapping Rain Water接雨水展开完整讲解题目语义、三种主流通用解法双重循环、动态规划、双指针以及单调栈思路并逐行剖析当前仓库 LeetCode-Go 中leetcode/0042.Trapping-Rain-Water目录下的 Go 实现与测试用例。读完本文你不仅能理解每个位置能接多少水 min(左侧最高, 右侧最高) − 当前高度这一核心抽象还能掌握 O(n) 时间、O(1) 空间的经典双指针写法及其正确性直觉并可直接在本地运行仓库测试验证结果。题目描述给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。示例中的高度图由数组[0,1,0,2,1,0,1,3,2,1,2,1]表示柱子宽度为 1数组元素即柱高该地形可以接6 个单位的雨水即图中蓝色区域。示例Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6逐列拆解验证每个下标对应一根宽度为 1 的柱子可积水高度 min(左侧最高, 右侧最高) − 当前柱高取非负值下标高度左侧最高右侧最高可接雨水00030110302013132130412315023261231732208232091321102310111300合计恰好为 6与题目输出一致。题目大意从 x 轴开始给出一个数组数组里面的数字代表从 (0,0) 点开始宽度为 1 个单位高度为数组元素的值。如果下雨了问这样一个容器能装多少单位的水换一种更直观的理解方式把数组想象成一面从左到右起伏的城墙剖面柱与柱之间天然形成若干个坑。雨水会填满每个坑直到从该坑向左看和向右看都看不到更高的墙为止。题目要求的正是这些坑中雨水体积的总和。由于每个柱子的宽度固定为 1问题退化为求每个位置能积攒的雨水高度再求和。解题思路核心抽象每个位置的水量 min(左侧最高, 右侧最高) − 当前高度本题的关键抽象如下针对每个下标 i找到它左边最大值leftMax右边的最大值rightMax然后min(leftMax, rightMax)就是该位置能够接到水的高度上限实际可接水量 max(0, min(leftMax, rightMax) − height[i])每个 i 的宽度固定为 1所以每个坑只需要求出高度即当前这个坑能积攒的雨水。最后依次将每个坑中的雨水相加即是能接到的雨水数。基于这一抽象可以推导出由朴素到最优的多种解法。朴素解法双重循环O(n²) / O(1)最直接的思路是对每个下标 i往左循环找到左侧最大值往右循环找到右侧最大值取二者较小者减去当前高度累加到结果中。func trapBruteForce(height []int) int { res : 0 for i : 1; i len(height)-1; i { leftMax, rightMax : 0, 0 for j : i; j 0; j-- { // 向左找最大值 if height[j] leftMax { leftMax height[j] } } for j : i; j len(height); j { // 向右找最大值 if height[j] rightMax { rightMax height[j] } } if min : leftMax; rightMax min { min rightMax } if v : min - height[i]; v 0 { res v } } return res }这样做时间复杂度高浪费了很多循环——每个下标都要向左右各扫描一遍整体复杂度为 O(n²)。它虽然正确但只适合规模很小的输入。动态规划解法预处理左右最大值数组O(n) / O(n)i 在从左往右的过程中是可以动态维护最大值的。因此可以先用两趟线性扫描分别预计算leftMax[i]从 0 到 i 的区间最大值含 i 自身rightMax[i]从 i 到 n−1 的区间最大值含 i 自身。然后每个位置只需 O(1) 查表累加func trapDP(height []int) int { n : len(height) if n 0 { return 0 } leftMax : make([]int, n) rightMax : make([]int, n) leftMax[0] height[0] for i : 1; i n; i { if height[i] leftMax[i-1] { leftMax[i] height[i] } else { leftMax[i] leftMax[i-1] } } rightMax[n-1] height[n-1] for i : n - 2; i 0; i-- { if height[i] rightMax[i1] { rightMax[i] height[i] } else { rightMax[i] rightMax[i1] } } res : 0 for i : 0; i n; i { m : leftMax[i] if rightMax[i] m { m rightMax[i] } if v : m - height[i]; v 0 { res v } } return res }时间 O(n)、额外空间 O(n)。该解法与min(左侧最大值, 右侧最大值)的抽象一一对应是最直观、最容易写对的版本。双指针解法两侧向中间收缩O(n) / O(1)这是本仓库实际采用的解法也是面试中推荐的最优写法。核心思想左指针从 0 开始往右扫右指针从最右边开始往左扫额外需要 2 个变量分别记住左边最大的高度maxLeft和右边最大高度maxRight遍历扫数组元素的过程中如果左指针的高度比右指针的高度小就不断地移动左指针否则移动右指针循环的终止条件是左右指针碰上以后就结束只要数组中元素的高度比保存的局部最大高度小就累加res的值否则更新局部最大高度最终解就是res的值。正确性直觉当height[left] height[right]时右指针位置已经存在一根不低于当前左指针高度的墙作为兜底因此左指针当前位置的储水量只由左侧已扫描到的最大高度maxLeft决定左侧最高墙封顶反之当右指针高度更小时对称地处理右指针。这一过程与动态规划版本逐位置计算min(左侧最高, 右侧最高) − 当前高度完全等价只是通过哪边矮就先处理哪边的方式把两个长度为 n 的辅助数组压缩成了两个变量空间降到 O(1)。此外每个数组里面的元素值可以想象成一个左右都有壁的圆柱筒例如示例中下标 2 的元素 0其左侧最大元素是 1下标 1所以 1 高度的水会装到它的上面因为想象成了左右都有筒壁而下标 5 的元素 0左侧最大是 2下标 3、右侧最大是 3下标 7因此它能接到 2 高度的水。边界情况说明数组长度不足 3如空数组、单元素、两元素时必然接不到水严格递增或严格递减的地形中每个位置的高度都会不断刷新maxLeft/maxRightres恒为 0。这些情况在下面的双指针实现中都会被自然处理无需特判。单调栈解法补充思路除上述三种主流解法外本题还常用单调递减栈处理从左到右遍历维护一个高度单调递减的栈当遇到比栈顶更高的柱子时说明出现了坑的右壁此时弹出栈顶作为坑底取新的栈顶左侧壁与当前柱子右侧壁中较矮者作为水位高度乘以两壁之间的宽度累加面积。该解法时间复杂度 O(n)、空间复杂度 O(n)适合作为对比学习的补充仓库本题实现未采用此方案。仓库源码实现逐行解析本题的完整实现位于 leetcode/0042.Trapping-Rain-Water 目录下源文件为42. Trapping Rain Water.go全文如下package leetcode func trap(height []int) int { res, left, right, maxLeft, maxRight : 0, 0, len(height)-1, 0, 0 for left right { if height[left] height[right] { if height[left] maxLeft { maxLeft height[left] } else { res maxLeft - height[left] } left } else { if height[right] maxRight { maxRight height[right] } else { res maxRight - height[right] } right-- } } return res }逐行拆解对应源文件第 322 行第 4 行变量初始化res累计总雨水量初始为 0left指向最左下标 0right指向最右下标len(height)-1maxLeft、maxRight分别记录左右两侧已扫描到的最大高度初始为 0。第 5 行循环终止条件for left right左右指针碰上以后循环结束——这正是原文档中循环的终止条件就是左右指针碰上以后就结束的实现。注意这里用而不是可以保证在指针相遇的那个位置也被正确结算相遇时两侧高度相同走左分支用maxLeft结算该点。第 612 行左分支当height[left] height[right]时处理左指针。若当前高度刷新了maxLeft则说明当前柱子本身就是左侧新的最高墙此处不可能积水只更新maxLeft不累加否则当前位置是一处坑能接maxLeft - height[left]的水累加到res然后left向右推进。第 1319 行右分支对称处理右指针。当height[right] maxRight时更新右侧最高墙否则累加maxRight - height[right]然后right--向左推进。第 22 行循环结束返回res即接到的雨水总量。这里有一个值得注意的对称细节左分支的更新条件是height[left] maxLeft严格大于才更新右分支是height[right] maxRight大于等于即更新。由于两侧分支的进入条件是/互补的这种写法配合left right的循环条件保证指针相遇位置不会被重复或遗漏结算读者可自行用示例数组逐指针推演验证。测试用例与运行验证同目录下的测试文件42. Trapping Rain Water_test.go使用本仓库统一的问题-参数-答案结构question42/para42/ans42组织用例package leetcode import ( fmt testing ) type question42 struct { para42 ans42 } // para 是参数 // one 代表第一个参数 type para42 struct { one []int } // ans 是答案 // one 代表第一个答案 type ans42 struct { one int } func Test_Problem42(t *testing.T) { qs : []question42{ { para42{[]int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}}, ans42{6}, }, } fmt.Printf(------------------------Leetcode Problem 42------------------------\n) for _, q : range qs { _, p : q.ans42, q.para42 fmt.Printf(【input】:%v 【output】:%v\n, p, trap(p.one)) } fmt.Printf(\n\n\n) }测试用例与题目示例完全一致输入[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]期望输出 6。运行方式如下仓库go.mod声明模块为github.com/halfrost/LeetCode-GoGo 版本要求go 1.19且通过 replace 指令将structures、template、ctl/util、ctl/models指向本地子目录go test -v ./leetcode/0042.Trapping-Rain-Water/或在题目目录内直接运行cd leetcode/0042.Trapping-Rain-Water go test -v -run Test_Problem42 .测试通过时输出PASS并打印形如【input】:[0 1 0 2 1 0 1 3 2 1 2 1] 【output】:6的调试信息。读者也可以复制该测试文件自行追加更多用例如空数组、递增/递减数组、等高地形的边界场景来验证双指针实现的鲁棒性。复杂度对比小结解法时间复杂度空间复杂度说明双重循环朴素O(n²)O(1)每个下标向左右各扫描一次最易理解但效率低动态规划预计算左右最大值O(n)O(n)与核心抽象一一对应最直观的 O(n) 写法双指针本仓库实现O(n)O(1)两侧向中间收缩最优时间与空间面试推荐单调栈O(n)O(n)用遇高弹出模拟坑的结算适合对比学习双指针版本每个下标恰好被访问一次由left或right其中一侧结算因此时间复杂度严格为 O(n)且不依赖任何额外数组空间复杂度 O(1)。在本仓库中的归类与延伸阅读本题在本仓库的题解站点中位于 website/content/ChapterFour/0001~0099/0042.Trapping-Rain-Water.md含英文版 website/content.en/ChapterFour/0001~0099/0042.Trapping-Rain-Water.md同时被归入双指针、栈、数组、动态规划等多个专题页见 website/content/ChapterTwo/Two_Pointers.md 与 website/content/ChapterTwo/Stack.md。读者可在这些专题目录下找到大量采用相同套路相向双指针、单调栈的题目对照学习。延伸练习建议本题的变体与姊妹题在仓库中均有实现例如接雨水问题的相关进阶题如最大矩形、柱状图中的最大矩形等可结合专题页按图索骥而每个位置由两侧最高值决定的抽象也可迁移到双向扫描类问题的思考中。若想验证仓库整体测试可在仓库根目录执行go test ./...gotest.sh脚本亦提供了批量测试入口。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考