题目来源

力扣每日一题；题序：42

我的题解

方法一 暴力解法

计算每一个位置的水有多少。找到每个位置的左侧最大值和右侧最大值，然后取两者中的较小的(水桶装水原理)，如果较小的大于当前位置，则表示该位置可以接雨水，接雨水的量：min(leftMax,rightMax)-cur
以前是能过的，现在好像过不了了

时间复杂度：O($n^2$)
空间复杂度：O(1)

java">class Solution {public  int trap(int[] height) {int res=0;for(int i=1;i<height.length-1;i++){//左侧最大值的位置int left=findMax(height,0,i);//右侧最大值的位置int right=findMax(height,i,height.length);//两者中的较小值int min=Math.min(height[left],height[right]);if(min>=height[i])res+=min-height[i];}return res;}//找最大值所在位置private  int findMax(int[] height, int s, int e) {int max=height[s];int index=s;for(int i=s;i<e;i++){if (height[i] > max) {max=height[i];index = i;}}return index;}
}

方法二 备忘录优化

在方法一中求左侧和右侧的最大值都会重复计算，因此可以提前预先计算每个位置的左侧和右侧最大值

时间复杂度：O(n)
空间复杂度：O(n)

java">public  int trap(int[] height) {int res=0;int n=height.length;int[] left=new int[n];int[] right=new int[n];left[0]=height[0];right[n-1]=height[n-1];for(int i=1;i<n;i++)left[i]=Math.max(left[i-1],height[i]);for(int i=n-2;i>=0;i--)right[i]=Math.max(right[i+1],height[i]);for(int i=1;i<height.length-1;i++){int min=Math.min(left[i],right[i]);res+=min-height[i];}return res;
}

方法三 双指针

两个指针分别指向还未被遍历的最左侧和最右侧，然后依次遍历每个位置，leftMax和rightMax不再是当前位置左侧和右侧的最大值，而是[0,left]和[right,end]中的最大值。

时间复杂度：O(n)
空间复杂度：O(1)

java">class Solution {public static int trap(int[] height) {int res=0;int left=0,right=height.length-1;int leftMax=height[left],rightMax=height[right];while(left<right){if(height[left]<height[right]){//找左边最大if(height[left]>leftMax)leftMax=height[left];elseres+=leftMax-height[left];left++;}else{//找右边最大if(height[right]>rightMax)rightMax=height[right];elseres+=rightMax-height[right];right--;}}return res;}
}

方法四 单调栈

该方法计算雨水量是横向计算每个水平面可以接的雨水量。
用单调栈计算能接的雨水总量。维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组 height 中的元素递减。
从左到右遍历数组，遍历到下标 iii 时，如果栈内至少有两个元素，记栈顶元素为 top，top 的下面一个元素是 left，则一定有 height[left]≥height[top]。如果 height[i]>height[top]，则得到一个可以接雨水的区域，该区域的宽度是 i−left−1，高度是 min⁡(height[left],height[i])−height[top]，根据宽度和高度即可计算得到该区域能接的雨水量。
为了得到 left，需要将 top 出栈。在对 top 计算能接的雨水量之后，left 变成新的 top，重复上述操作，直到栈变为空，或者栈顶下标对应的 height中的元素大于或等于 height[i]。
在对下标 i 处计算能接的雨水量之后，将 i 入栈，继续遍历后面的下标，计算能接的雨水量。遍历结束之后即可得到能接的雨水总量。

时间复杂度：O(n)
空间复杂度：O(n)

java">class Solution {public static int trap(int[] height) {int res=0;Stack<Integer> stack=new Stack<>();int i=0;while(i<height.length){while(!stack.isEmpty()&&height[stack.peek()]<height[i]){int low=stack.pop();if(stack.isEmpty())break;int min=Math.min(height[stack.peek()],height[i]);int width=i-stack.peek()-1;res+=width*(min-height[low]);}stack.push(i++);}return res;}
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~