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

没做出来，看的官解。

1. 动态规划的思想

当位于i处，i处能接水的体积=左侧最高点和右侧最高点的最小值（水桶原理）-自身的高度

classSolution{publicinttrap(int[]height){intsum=0;intn=height.length;int[]leftMax=newint[n];leftMax[0]=height[0];for(inti=1;i<n;i++){leftMax[i]=Math.max(leftMax[i-1],height[i]);}int[]rightMax=newint[n];rightMax[n-1]=height[n-1];for(inti=n-2;i>=0;i--){rightMax[i]=Math.max(rightMax[i+1],height[i]);}for(inti=0;i<n;i++){sum+=Math.min(rightMax[i],leftMax[i])-height[i];}returnsum;}}

2. 采用单调栈计算

只要有凹槽就可以储水，首先将元素放入单调栈中，然后循环数组与栈顶对比。
此时：如果该元素（相当于右侧）大于栈顶的元素（相当于底部）再加上栈顶的下一个元素（相当于左侧，单调栈，栈顶元素一定小于第二个元素）就形成了凹槽。

classSolution{publicinttrap(int[]height){intn=height.length;intres=0;Deque<Integer>stack=newArrayDeque<>();for(inti=0;i<n;i++){intright=i;while(!stack.isEmpty()&&height[right]>height[stack.peek()]){intbottom=stack.pop();if(stack.isEmpty()){// 左侧无元素，无法形成凹槽break;}intleft=stack.peek();intw=right-left-1;inth=Math.min(height[right],height[left])-height[bottom];res+=w*h;}stack.push(i);}returnres;}}

3. 采用双指针

按照动态规划的思路，只需要维护leftMax，rightMax两个变量就可以将空间降至O(1)

classSolution{publicinttrap(int[]height){intres=0;intleft=0,right=height.length-1;intleftMax=0,rightMax=0;while(left<right){leftMax=Math.max(leftMax,height[left]);rightMax=Math.max(rightMax,height[right]);if(leftMax<rightMax){// 根据水桶原理，leftMax比rightMaxx小，此时，无论右边多大，水超过leftMax就会溢出。res+=leftMax-height[left++];}else{res+=rightMax-height[right--];}}returnres;}}