LeetCode 第42题 接雨水

class Solution { public int trap(int[] height) { int ans 0; // 保存总共承接雨水总量 int left 0, right height.length - 1; // 左右双指针 int leftMax 0, rightMax 0; // left左侧最高柱子、right右侧最高柱子 while(left right) { // 更新左边最大高度 leftMax Math.max(leftMax, height[left]); // 更新右边最大高度 rightMax Math.max(rightMax, height[right]); if(height[left] height[right]) { // 左边柱子更低当前位置存水量 左侧最高高度 - 当前柱子高度 ans leftMax - height[left]; left; } else { // 右边柱子更低当前位置存水量 右侧最高高度 - 当前柱子高度 ans rightMax - height[right]; right--; } } return ans; } }一、核心算法思想双指针 O (n)、空间 O (1)基础理论单个位置蓄水量 min (当前位置左侧最高柱子当前位置右侧最高柱子) − 当前柱子高度定义左指针left起始于数组头部右指针right起始于数组尾部leftMax记录左指针遍历路径上的最高柱子rightMax记录右指针遍历路径上的最高柱子短板判定规则如果height[left] height[right]左侧为短板。此时leftMax就是左右两侧较小的最大值直接计算当前 left 位置雨水左指针右移如果height[left] height[right]右侧为短板。此时rightMax就是左右两侧较小的最大值直接计算当前 right 位置雨水右指针左移累加每个位置蓄水量指针相遇循环结束返回雨水总和。记忆口诀哪边柱子矮先算哪边蓄水量移动哪边指针。二、实例运行表格推演测试样例height [0,1,0,2,1,0,1,3,2,1,2,1]初始状态left0right11leftMax0rightMax0ans0leftrightheight[left]height[right]leftMaxrightMax大小对比当前格子雨水总水量 ans0110101left 矮0-0001111111相等走右侧逻辑1-1001101212left 矮1-1002100212left 矮1-0113102222相等走右侧逻辑2-201392122right 矮2-112382222相等走右侧逻辑2-202372323left 矮2-202471323left 矮2-113570323left 矮2-025671323left 矮2-116循环终止条件left7right7不满足leftright最终总雨水ans6。三、易错点与知识点总结1. 容易混淆题目区分LeetCode 11【盛最多水的容器】 VS LeetCode 42【接雨水】11 题求两根柱子之间形成的矩形面积整体区间蓄水42 题逐根竖柱单独计算垂直方向雨水每个位置受左右最高柱子限制两道题模型完全不同不要混用思路。2. 核心概念误区leftMax和rightMax不是全局最大值只是指针行进路径上记录的最大值。依靠「短板效应」不需要预先开辟数组存储每个位置左右最大值实现 O (1) 空间复杂度。3. 蓄水量不会为负数leftMax永远大于等于height[left]rightMax永远大于等于height[right]因此计算出的雨水数值≥0无需额外判断。