企业官网建设流程全解析

• 示例工程
• 教程

本文围绕《程序员面试金典（第 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}[i+1], \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.py

class 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.java

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; } }

C++

对应文件：Solution.cpp

class Solution { public: int trap(vector<int>& 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.go

func 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.ts

function 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.cs

public 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.swift

class 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 中的代码块保持同步：

这种"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^4，0 <= 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 中直接查看，适合作为同一模型的进阶练习。

八、总结与记忆要点

1. 蓄水公式是核心：位置 $i$ 的存水量 $= \min(\textit{leftMax}(i), \textit{rightMax}(i)) - \textit{height}[i]$，其中两个最大值都包含自身；
2. 前缀/后缀最大值可递推：一次左扫 + 一次右扫即可构造两个辅助数组，把暴力 $O(n^2)$ 降为 $O(n)$；
3. 特判先行：n < 3直接返回 0，两端位置天然贡献为 0；
4. 复杂度：时间 $O(n)$、空间 $O(n)$；
5. 进阶方向：双指针可将空间优化到 $O(1)$，可前往 42. 接雨水题解 横向对比。

掌握这一题，等于掌握了"接雨水"类问题的标准建模思路——它同时考察了数组遍历、动态规划递推和边界条件处理，是面试中性价比极高的经典题目。

• 示例工程
• 教程