题目给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。示例 1输入height [0,1,0,2,1,0,1,3,2,1,2,1]输出6解释上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水。示例 2输入height [4,2,0,3,2,5]输出9提示n height.length1 n 2 * 10^40 height[i] 10^5方法一暴力求解对于任意一个位置接雨水的量可以寻找其左右侧的最大值然后min(maxl,maxr)-当前值即为当前单位接水的量例如 i5其左侧最大值为2右侧最大值为3min(2,3)2那么i5这个单位接水的量即为2-02。例如i3其左侧最大值为2右侧最大值为3min(2,3)2那么单位接水量即为2-20.每个单位进行遍历其接水单位量得到总量timeout时间复杂度O(n^2)空间复杂度O(1)publicstaticinttrap(int[]height){intwater0;for(inti0;iheight.length;i){intleftMaxheight[i];intrightMaxheight[i];//左侧最大值for(intlefti;left0;left--){leftMaxMath.max(leftMax,height[left]);}//右侧最大值for(intrighti;rightheight.length;right){rightMaxMath.max(rightMax,height[right]);}intminMath.min(leftMax,rightMax);watermin-height[i];}returnwater;}方法二前缀最大值DP上面暴力方法中左边和右遍的最大值一直重复计算这里就提前对最大值进行保存即预先建立起 leftMax[i] 和 rightMax[i]。leftMax[i] 数组表示从 0~i 的最大值rightMax[i] 数组表示从 i~length-1 的最大值时间复杂度O(n)空间复杂度O(n)publicstaticinttrap(int[]height){intwater0;int[]leftMaxnewint[height.length];int[]rightMaxnewint[height.length];leftMax[0]height[0];rightMax[height.length-1]height[height.length-1];for(inti1;iheight.length;i){leftMax[i]Math.max(leftMax[i-1],height[i]);}for(intiheight.length-2;i0;i--){rightMax[i]Math.max(rightMax[i1],height[i]);}for(inti0;iheight.length;i){waterMath.min(leftMax[i],rightMax[i])-height[i];}returnwater;}方法三单调栈维护一个单调递减栈当发现入栈的元素不是递减的时候即形成了凹槽此时再依次弹出栈中的元素记录形成的雨水量时间复杂度O(n)空间复杂度O(n)publicstaticinttrap(int[]height){intwater0;DequeIntegerstacknewArrayDeque();for(inti0;iheight.length;i){while(!stack.isEmpty()height[i]height[stack.peek()]){//保存栈顶元素inttopstack.pop();if(stack.isEmpty()){break;}//下一个栈元素intleftstack.peek();water(Math.min(height[i],height[left])-height[top])*(i-left-1);}stack.push(i);}returnwater;}push()入栈把元素放到栈顶peek()查看栈顶但是不删除pop()弹出栈顶并删除push()放栈顶属于栈操作add()添加元素属于 Collection 接口方法四双指针维护一个左右指针left、right以及leftMax、rightMax。不断向中间逼近。谁矮谁决定水位矮的一方数值可以保留/定死并不断移动谁矮就先处理谁。可以理解为max较小一方计算水位是因为有另一头堵住无论中间柱子高或矮都不影响当前左右两侧最高对水的囤积时间复杂度O(n)空间复杂度O(1)publicinttrap(int[]height){intleft0;intrightheight.length-1;intleftMax0;intrightMax0;intsum0;while(leftright){// 更新左右最高柱子leftMaxMath.max(leftMax,height[left]);rightMaxMath.max(rightMax,height[right]);// 左边最高柱子低if(leftMaxrightMax){// 当前left位置接水sumleftMax-height[left];// 左指针向右移动left;}else{// 当前right位置接水sumrightMax-height[right];// 右指针向左移动right--;}}returnsum;}