★ FEATURED ARTICLE 示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本文围绕《程序员面试金典第 6 版》第 17.21 题「直方图的水量」Volume of Histogram展开以 doocs/leetcode 仓库lcci/17.21.Volume of Histogram目录下的题解文档为核心深入剖析「左右最高柱预处理 动态规划」的经典接水算法并给出 Python3、Java、C、Go、TypeScript、C#、Swift 七种语言的完整可运行实现。读完本文你将掌握接水量问题的数学模型、前缀/后缀最大值数组的构造技巧、复杂度分析方法以及它与 LeetCode 42「接雨水」的关系与进阶解法路径。一、题目背景出自《程序员面试金典》第 6 版本题收录于 lcci/17.21.Volume of Histogram 目录属于仓库中《程序员面试金典第 6 版》系列题解对应英文版文档见 lcci/17.21.Volume of Histogram/README_EN.md。该系列覆盖了原书中精选的 100 编程面试题难度标注为Hard困难是典型的面试高频考点它考察的是对水能存多少这个物理直觉的数学抽象能力以及能否将 $O(n^2)$ 的朴素做法优化到线性时间。从仓库目录结构看本专题目录下除了题解文档还配有与文档代码一一对应的独立源码文件Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.cs、Solution.swift这些源码与本专题文档README.md/README_EN.md中的代码块完全一致方便读者直接复制运行或对照学习。二、题目描述与示例给定一个直方图也称柱状图假设有人从上面源源不断地倒水最后直方图能存多少水量直方图的宽度为 1。上图由数组[0,1,0,2,1,0,1,3,2,1,2,1]表示每个柱子的宽度为 1蓝色部分即为被拦截的水共 6 个单位。示例输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6理解题目的几个关键点宽度固定为 1柱子是等宽的因此水量可以用高度差 × 宽度 1的累加来度量问题退化为纯高度计算水只能存留在凹槽里某个位置能否存水、能存多少完全取决于它左右两侧最高柱子的矮者两端边界不可能存水最左、最右的柱子外侧没有墙水会直接流走。三、核心思路从暴力扫描到动态规划题解文档中的思考过程thinking 部分给出了清晰的推导路径柱状图接水。按层或按柱向两侧找边界最坏平方。位置 $i$ 的水位是左右最高柱的较小者减去自身高度左右最高可预处理。$left[i]$、$right[i]$ 为两侧含自身的前缀/后缀最大值再求和 $\min(l,r)-h$。两端无法蓄水长度小于 $3$ 直接 $0$。3.1 朴素的暴力做法$O(n^2)$最直观的想法是对于每个位置 $i$分别向左、向右扫描找出左右两侧各自最高的柱子再计算该位置能接的水量。由于每个位置都要向两侧各扫描一遍总复杂度为 $O(n^2)$。当柱子数量较大时例如 $n$ 达到 $10^4$ 级别这种做法很容易超时。3.2 关键观察局部最优可以递推出来题解文档抓住了问题的本质位置 $i$ 左侧的最高柱只取决于 $i$ 及其左边的柱子右侧的最高柱只取决于 $i$ 及其右边的柱子。这意味着左侧最高柱可以通过一次从左到右的扫描滚动求出右侧最高柱可以通过一次从右到左的扫描滚动求出。于是两遍 $O(n)$ 扫描即可预处理出所有位置的左右最高值从而把整体复杂度从 $O(n^2)$ 降到 $O(n)$。这正是动态规划思想的应用用子问题前缀/后缀最大值的最优解递推构建全局解。3.3 蓄水公式位置 $i$ 能接的水量为$$\min(\textit{left}[i], \textit{right}[i]) - \textit{height}[i]$$即两侧较矮的那堵墙的高度减去当前位置自身柱子的高度。若该差值为正说明此处存在凹槽可以存水若为负或零则存水量为 0求和时差值为负的位置对总水量无贡献实际累加时只需保证不产生负值由于 $\min(\textit{left}[i], \textit{right}[i]) \ge \textit{height}[i]$ 恒成立差值为非负数。四、算法推导与正确性分析4.1 数组定义与递推公式我们定义两个数组含自身在内的边界最大值$\textit{left}[i]$下标 $i$ 位置及其左边所有柱子的最高高度$\textit{right}[i]$下标 $i$ 位置及其右边所有柱子的最高高度。它们的递推公式为$$\textit{left}[i] \max(\textit{left}[i-1], \textit{height}[i]), \quad \textit{left}[0] \textit{height}[0]$$$$\textit{right}[i] \max(\textit{right}[i1], \textit{height}[i]), \quad \textit{right}[n-1] \textit{height}[n-1]$$4.2 为什么这样定义是对的假设在位置 $i$ 处存水水必须被左右两侧各至少一根柱子挡住。若左侧最高柱为 $L$右侧最高柱为 $R$则水面最高只能到达 $\min(L, R)$再高就会从较矮一侧溢出。因此$$\text{位置 } i \text{ 的存水量} \min(\textit{left}[i], \textit{right}[i]) - \textit{height}[i]$$由于 $\textit{left}[i]$ 和 $\textit{right}[i]$ 都包含自身高度$\textit{height}[i]$而 $\min(\textit{left}[i], \textit{right}[i]) \ge \textit{height}[i]$累加时天然保证了存水量非负。4.3 边界与特判长度小于 3 必然存不住水少于 3 根柱子无法形成两侧有墙的凹槽直接返回 0。仓库中各语言实现均以if (n 3) return 0;形式处理两端位置自动归零第 0 位和第 $n-1$ 位虽然也参与求和但由于 $\min(\textit{left}[0], \textit{right}[0]) - \textit{height}[0]$ 中 $\textit{left}[0] \textit{height}[0]$若 $\textit{right}[0] \ge \textit{height}[0]$ 则差值为 0同理末位也为 0无需单独排除。4.4 复杂度分析时间复杂度$O(n)$需要两遍线性扫描构造left/right数组再加一遍线性求和空间复杂度$O(n)$额外使用两个长度为 $n$ 的数组。其中 $n$ 为数组的长度。五、多语言实现仓库完整代码以下代码全部摘自 lcci/17.21.Volume of Histogram/README_EN.md并与其目录下的Solution.*源码文件一一对应。Python3对应文件Solution.pyclass Solution: def trap(self, height: List[int]) - int: n len(height) if n 3: return 0 left [height[0]] * n right [height[-1]] * n for i in range(1, n): left[i] max(left[i - 1], height[i]) right[n - i - 1] max(right[n - i], height[n - i - 1]) return sum(min(l, r) - h for l, r, h in zip(left, right, height))实现细节解读left [height[0]] * n一次性初始化随后从左向右递推right[n - i - 1] max(right[n - i], height[n - i - 1])巧妙地在同一个循环里从右向左递推right数组当i从 1 递增到n-1时n-i-1从n-2递减到 0正好完成从右向左的填充最后用zip(left, right, height)三路并行求和一行代码完成 $\sum \min(l, r) - h$。Java对应文件Solution.javaclass Solution { public int trap(int[] height) { int n height.length; if (n 3) { return 0; } int[] left new int[n]; int[] right new int[n]; left[0] height[0]; right[n - 1] height[n - 1]; for (int i 1; i n; i) { left[i] Math.max(left[i - 1], height[i]); right[n - i - 1] Math.max(right[n - i], height[n - i - 1]); } int ans 0; for (int i 0; i n; i) { ans Math.min(left[i], right[i]) - height[i]; } return ans; } }C对应文件Solution.cppclass Solution { public: int trap(vectorint height) { int n height.size(); if (n 3) { return 0; } int left[n], right[n]; left[0] height[0]; right[n - 1] height[n - 1]; for (int i 1; i n; i) { left[i] max(left[i - 1], height[i]); right[n - i - 1] max(right[n - i], height[n - i - 1]); } int ans 0; for (int i 0; i n; i) { ans min(left[i], right[i]) - height[i]; } return ans; } };Go对应文件Solution.gofunc trap(height []int) (ans int) { n : len(height) if n 3 { return 0 } left : make([]int, n) right : make([]int, n) left[0], right[n-1] height[0], height[n-1] for i : 1; i n; i { left[i] max(left[i-1], height[i]) right[n-i-1] max(right[n-i], height[n-i-1]) } for i, h : range height { ans min(left[i], right[i]) - h } return }说明该 Go 实现使用了命名返回值ans函数体内直接return即可带回累加结果max/min为 Go 1.21 内置函数或由编译环境提供。TypeScript对应文件Solution.tsfunction trap(height: number[]): number { const n height.length; if (n 3) { return 0; } const left: number[] new Array(n).fill(height[0]); const right: number[] new Array(n).fill(height[n - 1]); for (let i 1; i n; i) { left[i] Math.max(left[i - 1], height[i]); right[n - i - 1] Math.max(right[n - i], height[n - i - 1]); } let ans 0; for (let i 0; i n; i) { ans Math.min(left[i], right[i]) - height[i]; } return ans; }C#对应文件Solution.cspublic class Solution { public int Trap(int[] height) { int n height.Length; if (n 3) { return 0; } int[] left new int[n]; int[] right new int[n]; left[0] height[0]; right[n - 1] height[n - 1]; for (int i 1; i n; i) { left[i] Math.Max(left[i - 1], height[i]); right[n - i - 1] Math.Max(right[n - i], height[n - i - 1]); } int ans 0; for (int i 0; i n; i) { ans Math.Min(left[i], right[i]) - height[i]; } return ans; } }Swift对应文件Solution.swiftclass Solution { func trap(_ height: [Int]) - Int { let n height.count if n 3 { return 0 } var left Int var right Int left[0] height[0] right[n - 1] height[n - 1] for i in 1..n { left[i] max(left[i - 1], height[i]) } for i in stride(from: n - 2, through: 0, by: -1) { right[i] max(right[i 1], height[i]) } var ans 0 for i in 0..n { ans min(left[i], right[i]) - height[i] } return ans } }说明Swift 版本将left与right的递推拆分为两个独立的循环其中right使用stride(from:through:by:)从n-2递减到 0 完成从右向左填充逻辑与其它语言的同循环双递推写法等价可读性更强。六、仓库源码佐证文档与实现的一致性本专题目录 lcci/17.21.Volume of Histogram 下每个语言的Solution.*文件与 README 中的代码块保持同步语言源码文件说明Python3Solution.py使用zip并行求和代码最简洁JavaSolution.java显式Math.max/Math.minCSolution.cpp使用定长数组int left[n], right[n]GoSolution.go命名返回值ansTypeScriptSolution.ts使用fill初始化数组C#Solution.cs与 Java 版结构对称SwiftSolution.swift拆分双循环stride反向遍历这种README 代码块 独立源码文件的双轨组织方式是整个仓库的通用约定读者既可以浏览文档快速理解思路也可以直接打开对应语言的Solution.*文件在本地编译运行、验证示例输出6。七、延伸与 LeetCode 42「接雨水」的关联与更多解法7.1 同源问题本题与 LeetCode 42「接雨水」Trapping Rain Water在数学模型上完全同源都是等宽柱状图求可容纳水量。中文题解文档在末尾明确列出了相似题目 42. 接雨水题解方便读者串联学习。区别仅在于题目来源17.21 出自《程序员面试金典》第 6 版面试场景42 是 LeetCode 独立编号题文档丰富度42 题的 题解文档 额外提供了 Rust、PHP 实现并给出了更完整的数据范围约束1 n 2 * 10^40 height[i] 10^5边界处理17.21 题解显式特判n 3而 42 题文档中的 PHP 实现还需兼容n 0的空数组场景。7.2 双指针优化方向在 42. 接雨水题解 文档中还收录了双指针解法以 PHP 实现为例其核心思想是维护left、right两个指针从两端向中间逼近同时维护leftMax、rightMax两个滚动最大值每次比较height[left]与height[right]哪一侧较矮就从哪一侧结算。较矮一侧的水量只取决于该侧的滚动最大值因为另一侧必然有更高的墙兜底无需再预计算整个right数组从而把空间复杂度从 $O(n)$ 降到 $O(1)$时间复杂度仍为 $O(n)$。从源码结构看17.21 题目录仅收录了前缀/后缀最大值这一种解法而双指针变体可以在 42 题的 README.md 中直接查看适合作为同一模型的进阶练习。八、总结与记忆要点蓄水公式是核心位置 $i$ 的存水量 $ \min(\textit{leftMax}(i), \textit{rightMax}(i)) - \textit{height}[i]$其中两个最大值都包含自身前缀/后缀最大值可递推一次左扫 一次右扫即可构造两个辅助数组把暴力 $O(n^2)$ 降为 $O(n)$特判先行n 3直接返回 0两端位置天然贡献为 0复杂度时间 $O(n)$、空间 $O(n)$进阶方向双指针可将空间优化到 $O(1)$可前往 42. 接雨水题解 横向对比。掌握这一题等于掌握了接雨水类问题的标准建模思路——它同时考察了数组遍历、动态规划递推和边界条件处理是面试中性价比极高的经典题目。赞分享示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐doocs/leetcode 题解精讲面试题 16.17 连续数列——Kadane 动态规划求最大子数组和doocs/leetcode 题解精讲面试题 16.17 连续数列——Kadane 动态规划求最大子数组和 导读 《程序员面试金典第 6 版》面试题 16示例工程教程doocs/leetcode 题解精讲《程序员面试金典》面试题 08.11 硬币——完全背包动态规划求组合数doocs/leetcode 题解精讲《程序员面试金典》面试题 08.11 硬币——完全背包动态规划求组合数 本文基于 doocs/leetcode http示例工程教程doocs/leetcode 题解精讲面试题 17.09「第 k 个数」Get Kth Magic Number——小根堆与三指针动态规划doocs/leetcode 题解精讲面试题 17.09「第 k 个数」Get Kth Magic Number——小根堆与三指针动态规划 本文以 doo示例工程教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
阅读完成 · 觉得有帮助？
