一、问题背景「接雨水」是数组与双指针领域中的经典问题也是算法面试中高频出现的一类边界约束问题。题目给定一个长度为n的非负整数数组height其中height[i]表示第i个位置上宽度为1的柱子高度。要求计算在这些柱子构成的地形中降雨后能够存储的雨水总量。形式化描述如下给定数组height[0], height[1], ..., height[n - 1]其中height[i] 0要求计算所有位置上方能够容纳的水量之和。例如height [0,1,0,2,1,0,1,3,2,1,2,1]其最终可以接到的雨水总量为6二、问题本质分析该问题表面上是一个模拟降雨过程的问题但从算法角度看它本质上是一个局部状态受左右边界共同约束的问题。对于任意位置i该位置能否存水并不只取决于当前位置的高度height[i]而是取决于其左侧和右侧是否存在足够高的边界。设leftMax[i] 表示位置 i 左侧包括自身在内的最大高度 rightMax[i] 表示位置 i 右侧包括自身在内的最大高度那么位置i上方能够形成的最高水位由左右两侧边界中的较小值决定即waterLevel[i] min(leftMax[i], rightMax[i])因此位置i能够容纳的雨水量为water[i] min(leftMax[i], rightMax[i]) - height[i]由于leftMax[i]和rightMax[i]都包含当前位置本身所以该值不会小于0。最终答案为answer Σ (min(leftMax[i], rightMax[i]) - height[i])其中i的取值范围为0 i n三、核心数学模型对数组height定义leftMax[i] max(height[0], height[1], ..., height[i])rightMax[i] max(height[i], height[i 1], ..., height[n - 1])则第i个位置的蓄水量为trap[i] min(leftMax[i], rightMax[i]) - height[i]因此总蓄水量为result Σ trap[i]该公式是解决本题的理论基础。其含义可以解释为当前位置的水位不能超过左侧最高边界也不能超过右侧最高边界。因此真正限制水位高度的是左右边界中较低的一侧。四、解法一动态规划预处理左右最大值最直接的做法是分别预处理每个位置左侧最高柱子和右侧最高柱子。1. 算法思想首先从左向右遍历数组计算leftMaxleftMax[i] max(leftMax[i - 1], height[i])然后从右向左遍历数组计算rightMaxrightMax[i] max(rightMax[i 1], height[i])最后再次遍历数组根据公式计算每个位置的蓄水量。2. C 代码实现#include iostream #include vector #include algorithm using namespace std; class Solution { public: int trap(vectorint height) { int n height.size(); if (n 2) { return 0; } vectorint leftMax(n); vectorint rightMax(n); leftMax[0] height[0]; for (int i 1; i n; i) { leftMax[i] max(leftMax[i - 1], height[i]); } rightMax[n - 1] height[n - 1]; for (int i n - 2; i 0; i--) { rightMax[i] max(rightMax[i 1], height[i]); } int result 0; for (int i 0; i n; i) { result min(leftMax[i], rightMax[i]) - height[i]; } return result; } };3. 算法正确性分析对于任意位置i若该位置能够存储雨水则必须存在左侧边界和右侧边界。左侧边界的最大高度为leftMax[i]右侧边界的最大高度为rightMax[i]由于水会从较低的一侧溢出因此位置i的最高水位只能达到min(leftMax[i], rightMax[i])该位置自身高度为height[i]所以其上方可容纳水量为min(leftMax[i], rightMax[i]) - height[i]算法对所有位置逐一计算该值并求和因此可以得到整个高度图的最大蓄水量。4. 复杂度分析该算法需要三次线性扫描第一次计算leftMax时间复杂度为O(n)。第二次计算rightMax时间复杂度为O(n)。第三次计算总蓄水量时间复杂度为O(n)。因此总时间复杂度为O(n)由于额外使用了两个长度为n的数组所以空间复杂度为O(n)五、解法二双指针空间优化虽然动态规划预处理方法逻辑清晰但它需要额外的数组空间。进一步观察可以发现并不一定需要提前存储每个位置的leftMax和rightMax。我们可以通过双指针在一次遍历过程中动态维护左右边界从而将空间复杂度优化到O(1)。六、双指针算法思想设置两个指针left 0 right n - 1分别指向数组的左右两端。同时维护两个变量leftMax rightMax其中leftMax 表示从左端到 left 位置之间的最大高度 rightMax 表示从右端到 right 位置之间的最大高度在每一步中比较height[left] height[right]若height[left] height[right]则说明右侧至少存在一个高度大于height[left]的柱子。因此当前位置left的右边界已经可以保证不低于当前左柱高度此时该位置的蓄水能力主要由leftMax决定。若height[right] height[left]则同理可以处理右侧位置此时右侧位置的蓄水能力主要由rightMax决定。七、双指针代码实现#include iostream #include vector using namespace std; class Solution { public: int trap(vectorint height) { int n height.size(); if (n 2) { return 0; } int left 0; int right n - 1; int leftMax 0; int rightMax 0; int result 0; while (left right) { if (height[left] height[right]) { if (height[left] leftMax) { leftMax height[left]; } else { result leftMax - height[left]; } left; } else { if (height[right] rightMax) { rightMax height[right]; } else { result rightMax - height[right]; } right--; } } return result; } };八、双指针算法的正确性证明双指针算法的核心在于每次只处理较矮一侧的指针位置。下面以处理左指针为例进行说明。当满足height[left] height[right]时说明在right位置存在一个高度大于height[left]的右侧边界。因此对于当前位置left而言右侧最大值一定不小于height[right]也必然大于height[left]。此时当前位置是否能够接水只取决于左侧已经扫描过的最大高度leftMax。如果height[left] leftMax说明当前位置本身成为新的左侧最高边界不可能在当前位置上方形成积水因此更新leftMax。如果height[left] leftMax说明当前位置低于左侧最高边界同时右侧又存在足够高的边界因此当前位置能够接水其接水量为leftMax - height[left]右指针的处理过程与左指针对称。由于每次移动一个指针并且每个位置最多被访问一次因此算法能够在线性时间内完成计算。九、示例分析以题目示例为例height [0,1,0,2,1,0,1,3,2,1,2,1]我们分析几个关键位置。位置 2height[2] 0其左侧最大高度为1其右侧最大高度为3因此该位置可接水min(1, 3) - 0 1位置 5height[5] 0其左侧最大高度为2其右侧最大高度为3因此该位置可接水min(2, 3) - 0 2位置 9height[9] 1其左侧最大高度为3其右侧最大高度为2因此该位置可接水min(3, 2) - 1 1最终各可蓄水位置的水量累加为1 1 2 1 1 6因此答案为6十、两种方法的比较方法时间复杂度空间复杂度特点预处理左右最大值O(n)O(n)思路直观便于理解双指针优化O(n)O(1)空间最优适合面试与工程实现预处理方法更容易从数学模型直接推导出来适合作为理解该问题的第一种解法。双指针方法则是在预处理思想基础上的进一步优化其本质是利用左右边界的单调维护避免存储完整的辅助数组。十一、算法设计启示「接雨水」问题体现了数组问题中一个常见的分析范式局部答案并不只由当前位置决定而是由当前位置两侧的全局信息共同决定。在本题中每个位置的蓄水量依赖于左侧最大高度 右侧最大高度 当前位置高度这种结构具有明显的边界约束特征。类似的问题还包括柱状图中最大的矩形 盛最多水的容器 单调栈相关区间问题它们都要求我们从局部元素出发分析其受到哪些边界条件限制。十二、总结「接雨水」是一道典型的边界约束型数组问题。其核心结论是任意位置的蓄水高度由其左侧最高柱子和右侧最高柱子中的较小值决定。因此当前位置的蓄水量可以表示为min(leftMax, rightMax) - height[i]基于这一结论可以得到两类常见算法第一类是预处理左右最大值数组时间复杂度为O(n)空间复杂度为O(n)。第二类是双指针优化方法时间复杂度为O(n)空间复杂度为O(1)。从算法学习角度看本题的重点并不是代码本身而是如何从物理现象中抽象出数学模型再由数学模型推导出可实现的高效算法。这也是算法设计中非常重要的一种能力将直观问题形式化将边界关系转化为可计算状态。
