一、题目给定一个非负整数数组height其中每个元素表示某一列柱子的高度要求计算这些柱子之间最多能接多少雨水。例如height [0,1,0,2,1,0,1,3]可以把它理解成一排高低不同的柱子。这道题最容易一开始不知道从哪里入手但真正核心其实只有一句每一列能接的水 min(左边最高柱子, 右边最高柱子) - 当前柱子高度也就是water[i] Math.min(leftMax[i], rightMax[i]) - height[i];只要这个公式理解了整道题就已经解决了一大半。二、为什么要看左右最高柱子假设当前位置height[i] 1左边最高柱子5右边最高柱子3那么水最多能涨到多高不能涨到5因为右边只有3超过 3 的水会从右侧流出去。所以真正能形成的水面高度是min(5,3) 3当前柱子本身高度是1所以当前位置能存3 - 1 2单位水。因此公式就是Math.min(leftMax[i], rightMax[i]) - height[i]三、这道题真正的核心不是“水”而是边界对于任意一个位置i水面 ---------------- 左墙 当前柱子 右墙能接多少水完全取决于左边最高墙 右边最高墙而且只能取较矮的一侧。所以可以形成一个固定思维接雨水不是看相邻柱子而是看当前位置左右两侧的最高边界。四、最直接的暴力思路对于每个位置i向左找最高柱子向右找最高柱子计算当前水量可以写成for (int i 0; i height.length; i) { int leftMax 0; int rightMax 0; for (int j 0; j i; j) { leftMax Math.max(leftMax, height[j]); } for (int j i; j height.length; j) { rightMax Math.max(rightMax, height[j]); } ans Math.min(leftMax, rightMax) - height[i]; }这个思路正确。但是每一个位置都重新扫描左右两边。时间复杂度O(n²)明显存在大量重复计算。五、优化思路提前把左右最大值算出来既然每个位置都要知道左边最高 每个位置都要知道右边最高那就提前保存。定义int[] leftMax new int[n]; int[] rightMax new int[n];其中leftMax[i] 从 0 到 i 的最高柱子而rightMax[i] 从 i 到 n-1 的最高柱子这样后面每个位置就不用重新扫描。六、最终代码这是我目前掌握并推荐先固定下来的版本class Solution { public int trap(int[] height) { // 每一列水量 // min(leftMax[i], rightMax[i]) - height[i] int n height.length; int[] leftMax new int[n]; int[] rightMax new int[n]; int ans 0; // 初始化左右边界 leftMax[0] height[0]; rightMax[n - 1] height[n - 1]; // 计算前缀最大值 for (int i 1; i n; i) { leftMax[i] Math.max(leftMax[i - 1], height[i]); } // 计算后缀最大值 for (int i n - 2; i 0; i--) { rightMax[i] Math.max(rightMax[i 1], height[i]); } // 累加每一列能够存的水 for (int i 0; i n; i) { ans Math.min(leftMax[i], rightMax[i]) - height[i]; } return ans; } }七、为什么 leftMax[0] height[0]代码leftMax[0] height[0];因为对于最左边这个位置0 ~ 0范围里只有它自己。所以左边最高柱子 height[0]因此leftMax[0] height[0];这是前缀最大值的初始条件。八、为什么 leftMax 要从 1 开始代码for (int i 1; i n; i) {因为leftMax[0]已经初始化好了。对于i 1开始我们可以使用leftMax[i - 1]也就是leftMax[0]所以自然从1开始。九、leftMax 的状态转移怎么理解核心leftMax[i] Math.max(leftMax[i - 1], height[i]);翻译成人话到当前位置i为止的最大高度要么是前面已经出现过的最大高度要么是当前柱子更高。例如height [0, 1, 0, 2, 1]计算leftMax[0] 0然后i 1 max(0,1) 1所以leftMax[1] 1继续i 2 max(1,0) 1所以leftMax[2] 1继续i 3 max(1,2) 2所以leftMax[3] 2最终height: 0 1 0 2 1 leftMax: 0 1 1 2 2十、rightMax 完全对称初始化rightMax[n - 1] height[n - 1];因为最后一个位置右边只有自己。然后从右往左for (int i n - 2; i 0; i--) {状态转移rightMax[i] Math.max(rightMax[i 1], height[i]);意思从当前位置i往右的最高柱子要么是右边已经找到的最大值要么是当前柱子。十一、为什么 rightMax 从 n - 2 开始因为rightMax[n - 1]已经初始化。而rightMax[i]需要依赖rightMax[i 1]所以第一个可以计算的位置就是n - 2例如数组长度n 5最后一个下标4已初始化。所以从3开始向左。十二、最终公式有了leftMax[i] rightMax[i]以后每一列水量直接Math.min(leftMax[i], rightMax[i]) - height[i]总水量ans Math.min(leftMax[i], rightMax[i]) - height[i];这就是整道题最终核心。十三、用一个小例子完整走一遍假设height [3,0,2]先计算leftMax得到[3,3,3]因为位置0 最大 3 位置1 max(3,0) 3 位置2 max(3,2) 3再计算rightMax得到[3,2,2]因为位置2 最大 2 位置1 max(2,0) 2 位置0 max(2,3) 3所以height [3,0,2] leftMax [3,3,3] rightMax [3,2,2]逐个计算水量。i 0min(3,3) - 3 0i 1min(3,2) - 0 2i 2min(3,2) - 2 0总水量2正确。十四、为什么最左边和最右边也可以直接计算直觉上最左边和最右边肯定接不了水。代码却写for (int i 0; i n; i)从头到尾全部算。为什么没问题因为最左边leftMax[0] height[0]所以min(leftMax[0], rightMax[0]) leftMax[0] height[0]实际上最终水量一定为0最右边同理。所以不需要特殊处理。十五、为什么水量不会是负数公式Math.min(leftMax[i], rightMax[i]) - height[i]因为leftMax[i]本身包含height[i]所以一定leftMax[i] height[i]同理rightMax[i] height[i]因此min(leftMax[i], rightMax[i]) height[i]所以水量 0不会出现负数。十六、这是不是动态规划可以把它理解成前缀 / 后缀 DP。因为leftMax[i]依赖leftMax[i - 1]而rightMax[i]依赖rightMax[i 1]都有明显的状态递推关系。但面试里说前后缀最大值其实会更直观。十七、复杂度分析一共进行了三次遍历。第一次计算 leftMax O(n)第二次计算 rightMax O(n)第三次计算答案 O(n)总时间O(n) O(n) O(n) O(n)所以时间复杂度O(n)额外创建leftMax rightMax两个长度为n的数组。所以空间复杂度O(n)十八、还能不能优化可以。当前时间 O(n) 空间 O(n)还可以进一步通过双指针将空间复杂度优化到O(1)但当前这版已经非常适合理解和面试保底。因为它直接对应最核心公式water[i] min(leftMax[i], rightMax[i]) - height[i]逻辑最清楚。十九、双指针优化的思想前后缀数组实际上是为了提前知道左边最高 右边最高但如果使用两个指针left right并同时维护leftMax rightMax就不需要两个数组。因此可以优化成时间 O(n) 空间 O(1)不过学习顺序应该是先理解每列公式 ↓ 再理解前后缀最大值 ↓ 最后学双指针空间优化而不是直接死背双指针。二十、面试讲法如果面试官让我讲我会这样回答对于任意位置i它能够接的水量取决于它左侧最高柱子和右侧最高柱子中较矮的那个因此当前水量为min(leftMax[i], rightMax[i]) - height[i]。为了避免对每个位置都重新向左右扫描我分别预处理一个前缀最大值数组leftMax和后缀最大值数组rightMax。leftMax[i] max(leftMax[i-1], height[i])rightMax[i] max(rightMax[i1], height[i])。最后遍历数组将每个位置的水量累加。整体时间复杂度 O(n)额外空间复杂度 O(n)。如果进一步要求 O(1) 空间可以使用双指针优化。这段就已经非常完整。二十一、最容易写错的地方1. leftMax 初始化错误应该leftMax[0] height[0];不能直接从0默认值开始递推而忽略第一个柱子。2. rightMax 初始化错误应该rightMax[n - 1] height[n - 1];3. rightMax 循环方向写反应该从右向左for (int i n - 2; i 0; i--)因为它依赖rightMax[i 1]4. 公式用了 max错误Math.max(leftMax[i], rightMax[i])应该Math.min(leftMax[i], rightMax[i])因为水面由较矮的边界决定。5. 忘记减当前柱子错误ans Math.min(leftMax[i], rightMax[i]);正确ans Math.min(leftMax[i], rightMax[i]) - height[i];因为柱子本身占据空间不是水。二十二、面试前 30 秒速记看到接雨水先想公式每一列水量 min(左边最高, 右边最高) - 当前高度代码模板int n height.length; int[] leftMax new int[n]; int[] rightMax new int[n]; leftMax[0] height[0]; for (int i 1; i n; i) { leftMax[i] Math.max(leftMax[i - 1], height[i]); } rightMax[n - 1] height[n - 1]; for (int i n - 2; i 0; i--) { rightMax[i] Math.max(rightMax[i 1], height[i]); } int ans 0; for (int i 0; i n; i) { ans Math.min(leftMax[i], rightMax[i]) - height[i]; } return ans;三条公式leftMax[i] max(leftMax[i-1], height[i]) rightMax[i] max(rightMax[i1], height[i]) water[i] min(leftMax[i], rightMax[i]) - height[i]复杂度时间 O(n) 空间 O(n)二十三、最终总结这道题最开始容易被图形吓到但真正拆开以后每一个位置其实都是独立计算当前位置能接多少水答案就是左右两边最高墙中较矮的那个 - 当前柱子高度也就是Math.min(leftMax[i], rightMax[i]) - height[i]为了避免每个位置重复向左右扫描通过前缀最大值 leftMax 后缀最大值 rightMax提前保存边界信息。最终思维链接雨水 ↓ 逐列计算 ↓ 需要左右最高墙 ↓ 前后缀最大值 ↓ O(n) 求解当前这版代码已经足够作为一个稳定的面试解法。后续如果继续优化只需要进一步把leftMax[] rightMax[]两个数组压缩成leftMax rightMax两个变量再配合双指针就可以做到O(n) 时间 O(1) 空间但无论怎么优化整道题最核心的公式始终不变water[i] min(leftMax[i], rightMax[i]) - height[i] LeetCode 42：接雨水｜前后最大值DP
一、题目给定一个非负整数数组height其中每个元素表示某一列柱子的高度要求计算这些柱子之间最多能接多少雨水。例如height [0,1,0,2,1,0,1,3]可以把它理解成一排高低不同的柱子。这道题最容易一开始不知道从哪里入手但真正核心其实只有一句每一列能接的水 min(左边最高柱子, 右边最高柱子) - 当前柱子高度也就是water[i] Math.min(leftMax[i], rightMax[i]) - height[i];只要这个公式理解了整道题就已经解决了一大半。二、为什么要看左右最高柱子假设当前位置height[i] 1左边最高柱子5右边最高柱子3那么水最多能涨到多高不能涨到5因为右边只有3超过 3 的水会从右侧流出去。所以真正能形成的水面高度是min(5,3) 3当前柱子本身高度是1所以当前位置能存3 - 1 2单位水。因此公式就是Math.min(leftMax[i], rightMax[i]) - height[i]三、这道题真正的核心不是“水”而是边界对于任意一个位置i水面 ---------------- 左墙 当前柱子 右墙能接多少水完全取决于左边最高墙 右边最高墙而且只能取较矮的一侧。所以可以形成一个固定思维接雨水不是看相邻柱子而是看当前位置左右两侧的最高边界。四、最直接的暴力思路对于每个位置i向左找最高柱子向右找最高柱子计算当前水量可以写成for (int i 0; i height.length; i) { int leftMax 0; int rightMax 0; for (int j 0; j i; j) { leftMax Math.max(leftMax, height[j]); } for (int j i; j height.length; j) { rightMax Math.max(rightMax, height[j]); } ans Math.min(leftMax, rightMax) - height[i]; }这个思路正确。但是每一个位置都重新扫描左右两边。时间复杂度O(n²)明显存在大量重复计算。五、优化思路提前把左右最大值算出来既然每个位置都要知道左边最高 每个位置都要知道右边最高那就提前保存。定义int[] leftMax new int[n]; int[] rightMax new int[n];其中leftMax[i] 从 0 到 i 的最高柱子而rightMax[i] 从 i 到 n-1 的最高柱子这样后面每个位置就不用重新扫描。六、最终代码这是我目前掌握并推荐先固定下来的版本class Solution { public int trap(int[] height) { // 每一列水量 // min(leftMax[i], rightMax[i]) - height[i] int n height.length; int[] leftMax new int[n]; int[] rightMax new int[n]; int ans 0; // 初始化左右边界 leftMax[0] height[0]; rightMax[n - 1] height[n - 1]; // 计算前缀最大值 for (int i 1; i n; i) { leftMax[i] Math.max(leftMax[i - 1], height[i]); } // 计算后缀最大值 for (int i n - 2; i 0; i--) { rightMax[i] Math.max(rightMax[i 1], height[i]); } // 累加每一列能够存的水 for (int i 0; i n; i) { ans Math.min(leftMax[i], rightMax[i]) - height[i]; } return ans; } }七、为什么 leftMax[0] height[0]代码leftMax[0] height[0];因为对于最左边这个位置0 ~ 0范围里只有它自己。所以左边最高柱子 height[0]因此leftMax[0] height[0];这是前缀最大值的初始条件。八、为什么 leftMax 要从 1 开始代码for (int i 1; i n; i) {因为leftMax[0]已经初始化好了。对于i 1开始我们可以使用leftMax[i - 1]也就是leftMax[0]所以自然从1开始。九、leftMax 的状态转移怎么理解核心leftMax[i] Math.max(leftMax[i - 1], height[i]);翻译成人话到当前位置i为止的最大高度要么是前面已经出现过的最大高度要么是当前柱子更高。例如height [0, 1, 0, 2, 1]计算leftMax[0] 0然后i 1 max(0,1) 1所以leftMax[1] 1继续i 2 max(1,0) 1所以leftMax[2] 1继续i 3 max(1,2) 2所以leftMax[3] 2最终height: 0 1 0 2 1 leftMax: 0 1 1 2 2十、rightMax 完全对称初始化rightMax[n - 1] height[n - 1];因为最后一个位置右边只有自己。然后从右往左for (int i n - 2; i 0; i--) {状态转移rightMax[i] Math.max(rightMax[i 1], height[i]);意思从当前位置i往右的最高柱子要么是右边已经找到的最大值要么是当前柱子。十一、为什么 rightMax 从 n - 2 开始因为rightMax[n - 1]已经初始化。而rightMax[i]需要依赖rightMax[i 1]所以第一个可以计算的位置就是n - 2例如数组长度n 5最后一个下标4已初始化。所以从3开始向左。十二、最终公式有了leftMax[i] rightMax[i]以后每一列水量直接Math.min(leftMax[i], rightMax[i]) - height[i]总水量ans Math.min(leftMax[i], rightMax[i]) - height[i];这就是整道题最终核心。十三、用一个小例子完整走一遍假设height [3,0,2]先计算leftMax得到[3,3,3]因为位置0 最大 3 位置1 max(3,0) 3 位置2 max(3,2) 3再计算rightMax得到[3,2,2]因为位置2 最大 2 位置1 max(2,0) 2 位置0 max(2,3) 3所以height [3,0,2] leftMax [3,3,3] rightMax [3,2,2]逐个计算水量。i 0min(3,3) - 3 0i 1min(3,2) - 0 2i 2min(3,2) - 2 0总水量2正确。十四、为什么最左边和最右边也可以直接计算直觉上最左边和最右边肯定接不了水。代码却写for (int i 0; i n; i)从头到尾全部算。为什么没问题因为最左边leftMax[0] height[0]所以min(leftMax[0], rightMax[0]) leftMax[0] height[0]实际上最终水量一定为0最右边同理。所以不需要特殊处理。十五、为什么水量不会是负数公式Math.min(leftMax[i], rightMax[i]) - height[i]因为leftMax[i]本身包含height[i]所以一定leftMax[i] height[i]同理rightMax[i] height[i]因此min(leftMax[i], rightMax[i]) height[i]所以水量 0不会出现负数。十六、这是不是动态规划可以把它理解成前缀 / 后缀 DP。因为leftMax[i]依赖leftMax[i - 1]而rightMax[i]依赖rightMax[i 1]都有明显的状态递推关系。但面试里说前后缀最大值其实会更直观。十七、复杂度分析一共进行了三次遍历。第一次计算 leftMax O(n)第二次计算 rightMax O(n)第三次计算答案 O(n)总时间O(n) O(n) O(n) O(n)所以时间复杂度O(n)额外创建leftMax rightMax两个长度为n的数组。所以空间复杂度O(n)十八、还能不能优化可以。当前时间 O(n) 空间 O(n)还可以进一步通过双指针将空间复杂度优化到O(1)但当前这版已经非常适合理解和面试保底。因为它直接对应最核心公式water[i] min(leftMax[i], rightMax[i]) - height[i]逻辑最清楚。十九、双指针优化的思想前后缀数组实际上是为了提前知道左边最高 右边最高但如果使用两个指针left right并同时维护leftMax rightMax就不需要两个数组。因此可以优化成时间 O(n) 空间 O(1)不过学习顺序应该是先理解每列公式 ↓ 再理解前后缀最大值 ↓ 最后学双指针空间优化而不是直接死背双指针。二十、面试讲法如果面试官让我讲我会这样回答对于任意位置i它能够接的水量取决于它左侧最高柱子和右侧最高柱子中较矮的那个因此当前水量为min(leftMax[i], rightMax[i]) - height[i]。为了避免对每个位置都重新向左右扫描我分别预处理一个前缀最大值数组leftMax和后缀最大值数组rightMax。leftMax[i] max(leftMax[i-1], height[i])rightMax[i] max(rightMax[i1], height[i])。最后遍历数组将每个位置的水量累加。整体时间复杂度 O(n)额外空间复杂度 O(n)。如果进一步要求 O(1) 空间可以使用双指针优化。这段就已经非常完整。二十一、最容易写错的地方1. leftMax 初始化错误应该leftMax[0] height[0];不能直接从0默认值开始递推而忽略第一个柱子。2. rightMax 初始化错误应该rightMax[n - 1] height[n - 1];3. rightMax 循环方向写反应该从右向左for (int i n - 2; i 0; i--)因为它依赖rightMax[i 1]4. 公式用了 max错误Math.max(leftMax[i], rightMax[i])应该Math.min(leftMax[i], rightMax[i])因为水面由较矮的边界决定。5. 忘记减当前柱子错误ans Math.min(leftMax[i], rightMax[i]);正确ans Math.min(leftMax[i], rightMax[i]) - height[i];因为柱子本身占据空间不是水。二十二、面试前 30 秒速记看到接雨水先想公式每一列水量 min(左边最高, 右边最高) - 当前高度代码模板int n height.length; int[] leftMax new int[n]; int[] rightMax new int[n]; leftMax[0] height[0]; for (int i 1; i n; i) { leftMax[i] Math.max(leftMax[i - 1], height[i]); } rightMax[n - 1] height[n - 1]; for (int i n - 2; i 0; i--) { rightMax[i] Math.max(rightMax[i 1], height[i]); } int ans 0; for (int i 0; i n; i) { ans Math.min(leftMax[i], rightMax[i]) - height[i]; } return ans;三条公式leftMax[i] max(leftMax[i-1], height[i]) rightMax[i] max(rightMax[i1], height[i]) water[i] min(leftMax[i], rightMax[i]) - height[i]复杂度时间 O(n) 空间 O(n)二十三、最终总结这道题最开始容易被图形吓到但真正拆开以后每一个位置其实都是独立计算当前位置能接多少水答案就是左右两边最高墙中较矮的那个 - 当前柱子高度也就是Math.min(leftMax[i], rightMax[i]) - height[i]为了避免每个位置重复向左右扫描通过前缀最大值 leftMax 后缀最大值 rightMax提前保存边界信息。最终思维链接雨水 ↓ 逐列计算 ↓ 需要左右最高墙 ↓ 前后缀最大值 ↓ O(n) 求解当前这版代码已经足够作为一个稳定的面试解法。后续如果继续优化只需要进一步把leftMax[] rightMax[]两个数组压缩成leftMax rightMax两个变量再配合双指针就可以做到O(n) 时间 O(1) 空间但无论怎么优化整道题最核心的公式始终不变water[i] min(leftMax[i], rightMax[i]) - height[i]