Leetcode 42. 接雨水-Toy模板网

这篇具有很好参考价值的文章主要介绍了Leetcode 42. 接雨水。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题意理解：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

左边的柱子和右边的柱子形成围栏，可以使中间能够积水

求最大的积水面积。h*w

解题思路：

1.横向求解

这里的单调栈采用的是横向求解。

求最右变第一个比他大的值作为右边界，栈顶第一个元素l=pop()作为底座，下下一个栈顶元素peek()作为左边界

则最高高度=min(height[i], height[peek()])

则积水面积高度=最高高度-底座=min(height[i], height[peek()])-l

积水的宽度=i-peek()-1

积水面积=h*w=(min(height[i], height[peek()])-l) * (i-peek()-1)

当且仅当stack有2个及以上元素时进行如上操作

若元素小于2，此时未形成积水面积，则pop()无法积水的高度元素

2.纵向求解

1.单调栈解题

public int trap(int[] height) {
        int result=0;
        Stack<Integer> stack=new Stack<>();
        stack.push(0);
        for(int i=1;i<height.length;i++){
            if(height[i]<=height[stack.peek()]){
                stack.push(i);
            }else{
                while((!stack.isEmpty())&&height[i]>height[stack.peek()]){
                   if(stack.size()>=2){
                       int mid=stack.pop();
                       int h=Math.min(height[i],height[stack.peek()])-height[mid];
                       int w=i-stack.peek()-1;
                       result+=w*h;
                   }else{
                       stack.pop();
                   }
                }
                stack.push(i);
            }
        }
        return  result;
    }