一.动态规划的解法第一步计算每个位置“左侧的最高柱子”我们从左向右遍历一次数组。对于第 i 个位置它的左侧最高柱子要么是 i-1 位置的左侧最高柱子要么就是 i-1 柱子本身的高度。取这两者的最大值即可。公式leftMax[i] Math.max(leftMax[i - 1], height[i - 1])第二步计算每个位置“右侧的最高柱子”我们从右向左遍历一次数组。对于第 i 个位置它的右侧最高柱子要么是 i1 位置的右侧最高柱子要么就是 i1 柱子本身的高度。取这两者的最大值即可。公式rightMax[i] Math.max(rightMax[i 1], height[i 1])第三步计算每个位置的积水量并累加再次从左向右遍历。根据“木桶效应”当前位置 i 的水位高度取决于左右最高柱子中较矮的那个。当前水位 Math.min(leftMax[i], rightMax[i])如果当前水位大于当前柱子的高度 height[i]说明能存水。当前位置积水量 当前水位 - height[i]将每个位置的积水量累加就是最终答案。publicclassTrappingRainWater{publicinttrap(int[]height){intnheight.length;// 边界条件如果柱子数量小于3肯定接不到水if(n3){return0;}// 1. 准备两个数组分别记录每个位置左侧和右侧的最高柱子int[]leftMaxnewint[n];int[]rightMaxnewint[n];// 2. 从左向右遍历计算每个位置左侧的最高柱子// 注意最左边的柱子索引0左侧没有柱子所以 leftMax[0] 0for(inti1;in;i){leftMax[i]Math.max(leftMax[i-1],height[i-1]);}// 3. 从右向左遍历计算每个位置右侧的最高柱子// 注意最右边的柱子索引n-1右侧没有柱子所以 rightMax[n-1] 0for(intin-2;i0;i--){rightMax[i]Math.max(rightMax[i1],height[i1]);}// 4. 遍历每个位置计算积水量并累加inttotalWater0;for(inti0;in;i){// 找出当前位置左右两侧最高柱子中较矮的那个木桶的短板intwaterLevelMath.min(leftMax[i],rightMax[i]);// 只有当水位高于当前柱子时才能存水if(waterLevelheight[i]){totalWaterwaterLevel-height[i];}}returntotalWater;}}二.双指针解法一、 核心思想木桶效应的极致利用在动态规划DP中我们计算位置 i 的水量时必须同时知道它左侧的全局最高和右侧的全局最高。但在双指针解法中我们利用了一个关键的数学事实木桶能装多少水取决于最短的那块木板。假设当前左侧最高是 leftMax右侧最高是 rightMax。如果 leftMax rightMax这说明左侧是短板。此时无论右侧还有多高的柱子当前位置left 指针所在位置的水位最高也只能达到 leftMax。因此我们根本不需要去管右侧未来的情况就可以绝对安全地计算出 left 位置的水量leftMax - height[left]。反之如果 rightMax leftMax说明右侧是短板我们就可以放心地计算 right 位置的水量。二、 详细推演过程初始化左指针 left 0右指针 right n - 1。记录左侧最高 leftMax height[0]右侧最高 rightMax height[n - 1]。总水量 totalWater 0。循环逼近当 left right 时比较短板判断 leftMax 和 rightMax 的大小。处理左侧如果 leftMax rightMax说明左侧是短板。计算当前 left 位置的积水量totalWater leftMax - height[left]。左指针右移left。更新左侧最高值leftMax Math.max(leftMax, height[left])。处理右侧如果 rightMax leftMax说明右侧是短板。计算当前 right 位置的积水量totalWater rightMax - height[right]。右指针左移right–。更新右侧最高值rightMax Math.max(rightMax, height[right])。结束当 left 和 right 相遇时所有位置的水量都已计算完毕。publicclassTrappingRainWater{publicinttrap(int[]height){intnheight.length;if(n3)return0;intleft0;intrightn-1;intleftMaxheight[left];intrightMaxheight[right];inttotalWater0;// 当左右指针未相遇时继续向中间逼近while(leftright){// 核心判断哪边是短板就先处理哪边if(leftMaxrightMax){// 左侧是短板计算 left 位置的水量left;// 先移动指针到下一个位置// 更新左侧最大值注意这里要用移动后的 left 对应的高度去更新leftMaxMath.max(leftMax,height[left]);// 累加水量当前左侧最高 - 当前柱子高度totalWaterleftMax-height[left];}else{// 右侧是短板或相等计算 right 位置的水量right--;// 先移动指针// 更新右侧最大值rightMaxMath.max(rightMax,height[right]);// 累加水量totalWaterrightMax-height[right];}}returntotalWater;}}解法对比双指针的优势空间极致O(1)摒弃了 DP 中需要额外开辟两个大数组的做法仅用几个变量彻底消除内存冗余避免大数据量下的内存溢出OOM。时间极致O(n)将 DP 的 3 次遍历压缩为 1 次遍历常数项开销最小达到理论最快极限。逻辑巧妙按需计算利用“木桶效应”哪边是短板就先算哪边边走边算消除了 DP 中的“无效全局计算”。
接雨水问题
一.动态规划的解法第一步计算每个位置“左侧的最高柱子”我们从左向右遍历一次数组。对于第 i 个位置它的左侧最高柱子要么是 i-1 位置的左侧最高柱子要么就是 i-1 柱子本身的高度。取这两者的最大值即可。公式leftMax[i] Math.max(leftMax[i - 1], height[i - 1])第二步计算每个位置“右侧的最高柱子”我们从右向左遍历一次数组。对于第 i 个位置它的右侧最高柱子要么是 i1 位置的右侧最高柱子要么就是 i1 柱子本身的高度。取这两者的最大值即可。公式rightMax[i] Math.max(rightMax[i 1], height[i 1])第三步计算每个位置的积水量并累加再次从左向右遍历。根据“木桶效应”当前位置 i 的水位高度取决于左右最高柱子中较矮的那个。当前水位 Math.min(leftMax[i], rightMax[i])如果当前水位大于当前柱子的高度 height[i]说明能存水。当前位置积水量 当前水位 - height[i]将每个位置的积水量累加就是最终答案。publicclassTrappingRainWater{publicinttrap(int[]height){intnheight.length;// 边界条件如果柱子数量小于3肯定接不到水if(n3){return0;}// 1. 准备两个数组分别记录每个位置左侧和右侧的最高柱子int[]leftMaxnewint[n];int[]rightMaxnewint[n];// 2. 从左向右遍历计算每个位置左侧的最高柱子// 注意最左边的柱子索引0左侧没有柱子所以 leftMax[0] 0for(inti1;in;i){leftMax[i]Math.max(leftMax[i-1],height[i-1]);}// 3. 从右向左遍历计算每个位置右侧的最高柱子// 注意最右边的柱子索引n-1右侧没有柱子所以 rightMax[n-1] 0for(intin-2;i0;i--){rightMax[i]Math.max(rightMax[i1],height[i1]);}// 4. 遍历每个位置计算积水量并累加inttotalWater0;for(inti0;in;i){// 找出当前位置左右两侧最高柱子中较矮的那个木桶的短板intwaterLevelMath.min(leftMax[i],rightMax[i]);// 只有当水位高于当前柱子时才能存水if(waterLevelheight[i]){totalWaterwaterLevel-height[i];}}returntotalWater;}}二.双指针解法一、 核心思想木桶效应的极致利用在动态规划DP中我们计算位置 i 的水量时必须同时知道它左侧的全局最高和右侧的全局最高。但在双指针解法中我们利用了一个关键的数学事实木桶能装多少水取决于最短的那块木板。假设当前左侧最高是 leftMax右侧最高是 rightMax。如果 leftMax rightMax这说明左侧是短板。此时无论右侧还有多高的柱子当前位置left 指针所在位置的水位最高也只能达到 leftMax。因此我们根本不需要去管右侧未来的情况就可以绝对安全地计算出 left 位置的水量leftMax - height[left]。反之如果 rightMax leftMax说明右侧是短板我们就可以放心地计算 right 位置的水量。二、 详细推演过程初始化左指针 left 0右指针 right n - 1。记录左侧最高 leftMax height[0]右侧最高 rightMax height[n - 1]。总水量 totalWater 0。循环逼近当 left right 时比较短板判断 leftMax 和 rightMax 的大小。处理左侧如果 leftMax rightMax说明左侧是短板。计算当前 left 位置的积水量totalWater leftMax - height[left]。左指针右移left。更新左侧最高值leftMax Math.max(leftMax, height[left])。处理右侧如果 rightMax leftMax说明右侧是短板。计算当前 right 位置的积水量totalWater rightMax - height[right]。右指针左移right–。更新右侧最高值rightMax Math.max(rightMax, height[right])。结束当 left 和 right 相遇时所有位置的水量都已计算完毕。publicclassTrappingRainWater{publicinttrap(int[]height){intnheight.length;if(n3)return0;intleft0;intrightn-1;intleftMaxheight[left];intrightMaxheight[right];inttotalWater0;// 当左右指针未相遇时继续向中间逼近while(leftright){// 核心判断哪边是短板就先处理哪边if(leftMaxrightMax){// 左侧是短板计算 left 位置的水量left;// 先移动指针到下一个位置// 更新左侧最大值注意这里要用移动后的 left 对应的高度去更新leftMaxMath.max(leftMax,height[left]);// 累加水量当前左侧最高 - 当前柱子高度totalWaterleftMax-height[left];}else{// 右侧是短板或相等计算 right 位置的水量right--;// 先移动指针// 更新右侧最大值rightMaxMath.max(rightMax,height[right]);// 累加水量totalWaterrightMax-height[right];}}returntotalWater;}}解法对比双指针的优势空间极致O(1)摒弃了 DP 中需要额外开辟两个大数组的做法仅用几个变量彻底消除内存冗余避免大数据量下的内存溢出OOM。时间极致O(n)将 DP 的 3 次遍历压缩为 1 次遍历常数项开销最小达到理论最快极限。逻辑巧妙按需计算利用“木桶效应”哪边是短板就先算哪边边走边算消除了 DP 中的“无效全局计算”。
