[Java][Leetcode hard] 42. 接雨水

没做出来看的官解。1. 动态规划的思想当位于i处i处能接水的体积左侧最高点和右侧最高点的最小值水桶原理-自身的高度classSolution{publicinttrap(int[]height){intsum0;intnheight.length;int[]leftMaxnewint[n];leftMax[0]height[0];for(inti1;in;i){leftMax[i]Math.max(leftMax[i-1],height[i]);}int[]rightMaxnewint[n];rightMax[n-1]height[n-1];for(intin-2;i0;i--){rightMax[i]Math.max(rightMax[i1],height[i]);}for(inti0;in;i){sumMath.min(rightMax[i],leftMax[i])-height[i];}returnsum;}}2. 采用单调栈计算只要有凹槽就可以储水首先将元素放入单调栈中然后循环数组与栈顶对比。此时如果该元素相当于右侧大于栈顶的元素相当于底部再加上栈顶的下一个元素相当于左侧单调栈栈顶元素一定小于第二个元素就形成了凹槽。classSolution{publicinttrap(int[]height){intnheight.length;intres0;DequeIntegerstacknewArrayDeque();for(inti0;in;i){intrighti;while(!stack.isEmpty()height[right]height[stack.peek()]){intbottomstack.pop();if(stack.isEmpty()){// 左侧无元素无法形成凹槽break;}intleftstack.peek();intwright-left-1;inthMath.min(height[right],height[left])-height[bottom];resw*h;}stack.push(i);}returnres;}}3. 采用双指针按照动态规划的思路只需要维护leftMaxrightMax两个变量就可以将空间降至O(1)classSolution{publicinttrap(int[]height){intres0;intleft0,rightheight.length-1;intleftMax0,rightMax0;while(leftright){leftMaxMath.max(leftMax,height[left]);rightMaxMath.max(rightMax,height[right]);if(leftMaxrightMax){// 根据水桶原理leftMax比rightMaxx小此时无论右边多大水超过leftMax就会溢出。resleftMax-height[left];}else{resrightMax-height[right--];}}returnres;}}