LeetCode：42. 接雨水

简介

题目链接：https://leetcode.cn/problems/trapping-rain-water/description/

解决方式：数组 + 暴力枚举 / 动态规划 / 双指针

这是作者学习众多大神的思路进行解题的步骤，很推荐大家解题的时候去看看题解里面大佬们的思路、想法！

暴力枚举

思路：对于“接雨水”问题，暴力枚举的思路非常直观：对于每个柱子，它上方能接的雨水量取决于它左边最高柱子和右边最高柱子中的较小者，再减去它自身的高度。如果这个差值是正数，就说明能积水。

classSolution{publicinttrap(int[]height){// 结果intwater=0;// 迭代for(inti=0;i<height.length;i++){// 当前柱子高度inth=height[i];// 向左寻找左侧最高元素（包括当前元素）intleftHeight=0;for(intleft=0;left<=i;left++){leftHeight=Math.max(leftHeight,height[left]);}// 向右寻找右侧最高元素（包括当前元素）intrightHeight=0;for(intright=i;right<height.length;right++){rightHeight=Math.max(rightHeight,height[right]);}// 公式。两侧较小元素值减去当前元素值intw=Math.min(leftHeight,rightHeight)-h;// 结果大于零，则可以接雨水if(w>0){water+=w;}}// 返回结果returnwater;}}

动态规划

思路：暴力枚举的方法由于查找左右两侧最大元素时都是从零开始，所以时间开销太大。我们可以通过记忆化的方式对其进行优化。当前元素的左侧最大值是前一个元素的左侧最大值与当前元素进行比较后的最大值，同理，右侧最大值是下一个元素的右侧最大值与当前元素进行比较后的最大值。我们可以先通过两个循环将左右两侧的最大值计算出来，后续迭代数组的时候就不用再进行计算了，也防止了重复计算的可能。

classSolution{publicinttrap(int[]height){// 总水量inttotalWater=0;// 数组每一元素的左侧最大值数组int[]leftMax=newint[height.length];leftMax[0]=height[0];for(inti=1;i<height.length;i++){leftMax[i]=Math.max(leftMax[i-1],height[i]);}// 数组每一个元素右侧的最大值数组int[]rightMax=newint[height.length];rightMax[height.length-1]=height[height.length-1];for(inti=height.length-2;i>=0;i--){rightMax[i]=Math.max(rightMax[i+1],height[i]);}// 迭代数组for(inti=0;i<height.length;i++){intwater=Math.min(leftMax[i],rightMax[i])-height[i];if(water>0){totalWater+=water;}}// 返回结果returntotalWater;}}

双指针

思路：动态规划会预先将左右两侧的最大值计算并存储下来，会有一定的空间开销。我们可以借助双指针，边迭代边计算，进行进一步的优化。双指针，一个指针指向数组左侧，一个指针指向数组右侧。循环过程中，每次只会移动一个指针。移动左指针，则说明右侧最大值比左侧最大值大，左指针指向的元素的水量取决于左侧最大值。同理，移动右指针，则说明左侧最大值大于等于右侧最大值，右指针指向的元素的水量取决于右侧最大值。

classSolution{publicinttrap(int[]height){// 总水量inttotalWater=0;// 双指针intleft=0;intright=height.length-1;// 两侧最大值intleftMax=0;intrightMax=0;// 迭代数组while(left<right){// 右侧最大值大于左侧最大值if(height[left]<height[right]){// 水量由左侧最大值决定if(height[left]>=leftMax){// 此时左侧最大值 - 当前元素 <= 0（当前元素最大），无法接水// 更新左侧最大值leftMax=height[left];}else{// 此时左侧最大值 - 当前元素 > 0，可以接水totalWater+=leftMax-height[left];}// 移动左指针left++;}else{// 左侧最大值大于等于右侧最大值// 水量由右侧最大值决定if(height[right]>=rightMax){// 此时右侧最大值 - 当前元素 <= 0（当前元素最大），无法接水// 更新右侧最大值rightMax=height[right];}else{// 此时右侧最大值 - 当前元素 > 0，可以接水totalWater+=rightMax-height[right];}// 移动右指针right--;}}// 返回结果returntotalWater;}}