LeetCode：42. 接雨水

简介题目链接https://leetcode.cn/problems/trapping-rain-water/description/解决方式数组 暴力枚举 / 动态规划 / 双指针这是作者学习众多大神的思路进行解题的步骤很推荐大家解题的时候去看看题解里面大佬们的思路、想法暴力枚举思路对于“接雨水”问题暴力枚举的思路非常直观对于每个柱子它上方能接的雨水量取决于它左边最高柱子和右边最高柱子中的较小者再减去它自身的高度。如果这个差值是正数就说明能积水。classSolution{publicinttrap(int[]height){// 结果intwater0;// 迭代for(inti0;iheight.length;i){// 当前柱子高度inthheight[i];// 向左寻找左侧最高元素包括当前元素intleftHeight0;for(intleft0;lefti;left){leftHeightMath.max(leftHeight,height[left]);}// 向右寻找右侧最高元素包括当前元素intrightHeight0;for(intrighti;rightheight.length;right){rightHeightMath.max(rightHeight,height[right]);}// 公式。两侧较小元素值减去当前元素值intwMath.min(leftHeight,rightHeight)-h;// 结果大于零则可以接雨水if(w0){waterw;}}// 返回结果returnwater;}}动态规划思路暴力枚举的方法由于查找左右两侧最大元素时都是从零开始所以时间开销太大。我们可以通过记忆化的方式对其进行优化。当前元素的左侧最大值是前一个元素的左侧最大值与当前元素进行比较后的最大值同理右侧最大值是下一个元素的右侧最大值与当前元素进行比较后的最大值。我们可以先通过两个循环将左右两侧的最大值计算出来后续迭代数组的时候就不用再进行计算了也防止了重复计算的可能。classSolution{publicinttrap(int[]height){// 总水量inttotalWater0;// 数组每一元素的左侧最大值数组int[]leftMaxnewint[height.length];leftMax[0]height[0];for(inti1;iheight.length;i){leftMax[i]Math.max(leftMax[i-1],height[i]);}// 数组每一个元素右侧的最大值数组int[]rightMaxnewint[height.length];rightMax[height.length-1]height[height.length-1];for(intiheight.length-2;i0;i--){rightMax[i]Math.max(rightMax[i1],height[i]);}// 迭代数组for(inti0;iheight.length;i){intwaterMath.min(leftMax[i],rightMax[i])-height[i];if(water0){totalWaterwater;}}// 返回结果returntotalWater;}}双指针思路动态规划会预先将左右两侧的最大值计算并存储下来会有一定的空间开销。我们可以借助双指针边迭代边计算进行进一步的优化。双指针一个指针指向数组左侧一个指针指向数组右侧。循环过程中每次只会移动一个指针。移动左指针则说明右侧最大值比左侧最大值大左指针指向的元素的水量取决于左侧最大值。同理移动右指针则说明左侧最大值大于等于右侧最大值右指针指向的元素的水量取决于右侧最大值。classSolution{publicinttrap(int[]height){// 总水量inttotalWater0;// 双指针intleft0;intrightheight.length-1;// 两侧最大值intleftMax0;intrightMax0;// 迭代数组while(leftright){// 右侧最大值大于左侧最大值if(height[left]height[right]){// 水量由左侧最大值决定if(height[left]leftMax){// 此时左侧最大值 - 当前元素 0当前元素最大无法接水// 更新左侧最大值leftMaxheight[left];}else{// 此时左侧最大值 - 当前元素 0可以接水totalWaterleftMax-height[left];}// 移动左指针left;}else{// 左侧最大值大于等于右侧最大值// 水量由右侧最大值决定if(height[right]rightMax){// 此时右侧最大值 - 当前元素 0当前元素最大无法接水// 更新右侧最大值rightMaxheight[right];}else{// 此时右侧最大值 - 当前元素 0可以接水totalWaterrightMax-height[right];}// 移动右指针right--;}}// 返回结果returntotalWater;}}