一、题目背景介绍题目原文给定n个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。示例输入height [0,1,0,2,1,0,1,3,2,1,2,1]示例输出6核心解题原理铺垫单个位置能储存的雨水计算公式 $$water[i] \min(左侧最高柱子高度,\ 右侧最高柱子高度) - 当前柱子高$$ 要求结果不能小于 0柱子本身很高无法存水时存水量取 0把数组所有下标位置的存水量累加就是总接雨体积。 拿示例下标 2数值 0举例左边最高是 1、右边最高是 2取最小值 1$$1-0$$这个格子可以存 1 单位雨水逐个点位求和最终总和为 6。二、方案 1暴力双重循环直观易懂适合新手理解逻辑算法思路遍历数组每一个下标i内层向左扫描找出[0,i-1]区间的柱子最大值leftMax内层向右扫描找出[i1,len-1]区间的柱子最大值rightMax按公式计算点位存水量负数直接归 0累加全局结果Java 完整代码public class TrapRainBrute { public int trap(int[] height) { int totalWater 0; int len height.length; // 下标首尾位置左右无围挡一定无法存水直接跳过 for(int i 1; i len - 1; i){ int leftMax 0; // 遍历左侧找最高柱 for(int l 0; l i; l){ leftMax Math.max(leftMax, height[l]); } int rightMax 0; // 遍历右侧找最高柱 for(int r i 1; r len; r){ rightMax Math.max(rightMax, height[r]); } int cur Math.min(leftMax, rightMax) - height[i]; totalWater Math.max(cur, 0); } return totalWater; } public static void main(String[] args) { TrapRainBrute solution new TrapRainBrute(); int[] input {0,1,0,2,1,0,1,3,2,1,2,1}; System.out.println(solution.trap(input)); // 控制台打印结果6 } }复杂度分析时间复杂度$$O(n^2$$外层循环遍历 n 次每个点位左右各做一次线性扫描数据量偏大时会超时空间复杂度$$O(1$$仅使用若干临时变量无额外数组开销三、方案 2动态规划预处理优化时间工业场景常用算法思路暴力解法重复做大量区间最大值扫描动态规划提前做预处理新建leftMaxDp数组leftMaxDp[i]记录下标i左侧含自身柱子的最大高度从左向右遍历填充新建rightMaxDp数组rightMaxDp[i]记录下标i右侧含自身柱子的最大高度从右向左遍历填充遍历所有下标套用存水公式累加总和Java 完整代码public class TrapRainDp { public int trap(int[] height) { int len height.length; if(len 2) return 0; int[] leftMaxDp new int[len]; int[] rightMaxDp new int[len]; leftMaxDp[0] height[0]; // 从左预处理左侧最大值 for(int i 1; i len; i){ leftMaxDp[i] Math.max(leftMaxDp[i - 1], height[i]); } rightMaxDp[len - 1] height[len - 1]; // 从右预处理右侧最大值 for(int i len - 2; i 0; i--){ rightMaxDp[i] Math.max(rightMaxDp[i 1], height[i]); } int totalWater 0; for(int i 0; i len; i){ totalWater Math.min(leftMaxDp[i], rightMaxDp[i]) - height[i]; } return totalWater; } public static void main(String[] args) { TrapRainDp solution new TrapRainDp(); int[] input {0,1,0,2,1,0,1,3,2,1,2,1}; System.out.println(solution.trap(input)); // 输出6 } }复杂度分析时间复杂度$$O(n$$三轮线性遍历数组不存在嵌套循环空间复杂度$$O(n$$需要两个长度和入参一致的 DP 数组做预处理存储四、方案 3双指针最优空间面试高频标准答案算法原理用左右指针left起始位置 0、right末尾位置len-1双向逼近同步维护两侧动态最大值leftMax、rightMax若leftMax rightMax左侧围挡上限更小left位置的储水量由左边挡板约束计算left点位雨水左指针右移更新左侧最大值反之右侧挡板约束储水量处理right点位雨水右指针左移更新右侧最大值 全程不依赖额外 DP 数组原地完成计算Java 完整代码public class TrapRainTwoPointer { public int trap(int[] height) { int len height.length; if(len 2) return 0; int left 0, right len - 1; int leftMax 0, rightMax 0; int totalWater 0; while(left right){ leftMax Math.max(leftMax, height[left]); rightMax Math.max(rightMax, height[right]); if(leftMax rightMax){ totalWater leftMax - height[left]; left; }else{ totalWater rightMax - height[right]; right--; } } return totalWater; } public static void main(String[] args) { TrapRainTwoPointer solution new TrapRainTwoPointer(); int[] input {0,1,0,2,1,0,1,3,2,1,2,1}; System.out.println(solution.trap(input)); // 输出6 } }复杂度分析时间复杂度$$O(n$$左右指针只会相向移动数组仅遍历 1 次空间复杂度$$O(1$$只定义基础整型变量无数组、容器类额外内存占用五、三种方案横向对比 面试答题建议实现方案时间复杂度空间复杂度适用场景暴力双重循环$$O(n^2$$$$O(1$$算法入门理解原理、小规模数据调试动态规划预处理$$O(n$$$$O(n$$工程开发、代码可读性优先的业务场景双向双指针$$O(n$$$$O(1$$算法笔试、技术面试追求最优空间性能踩坑避坑总结数组长度小于 3 时柱子不足 3 根无法围成凹槽直接返回 0规避数组下标越界、负数储水量问题储水量公式结果出现负数当前柱子高于两侧挡板必须归零不能做负数累加双指针不要写反指针移动逻辑哪边挡板上限更小就先结算哪一侧点位的雨水六、拓展延伸单调栈补充思路除上面三类写法该题还能借助单调递减栈做解法遍历柱子栈内存放柱子下标遇到更高柱子时弹出栈顶作为凹槽底部用新柱子与栈内新栈顶作为左右围挡结算雨水时间复杂度$$O(n$$、空间$$O(n$$适合延伸练习栈结构的应用场景。七、结语接雨水是数组区间最值类算法的标杆题目从暴力循环到 DP 预处理再优化成双指针完整体现了「先理解朴素逻辑、再做冗余扫描优化、最后压缩内存开销」通用算法优化思路在字节、阿里等大厂的 Java 后端算法笔试中出现频次很高建议熟练掌握双指针写法能兼顾时间、空间两项性能指标。