[数据结构与算法]接雨水--动态规划和单调栈

接雨水

动态规划的思想是，每一个柱子上都有可能接到水，如果利用两个数组维护当前i表示当前i 左边的最大值，和当前i右边的最大值，
然后i 能接的雨水就是左右最小值减去当前的i的高度。

class Solution {
    public int trap(int[] height) {
        int n= height.length;
        int []left= new int [n];
        int leftMax=height[0];
        for(int i=0;i<n;++i){
            if(height[i]>leftMax){
                leftMax=height[i];
            }
            left[i]=leftMax;
        }

        int []right=new int [n];
        int rightMax=height[n-1];
        for(int i=n-1;i>=0;--i){
            if(height[i]>rightMax){
                rightMax=height[i];
            }
            right[i]=rightMax;
        }

        int sum =0;
        for(int i =0;i<n;++i){
            sum+=Math.min(right[i],left[i])-height[i];
        }
        return sum;
        }
}

单调栈的思想是利用下降坡度会形成洼地，当有一根柱子比较高的时候就可以形成接雨水。
重点和难点是不知道如何判断回退几步，然后算出回退点的距离加上接雨水的高度。

class Solution {
    public int trap(int[] height) {
        //第二种方法，单调栈。
        Stack<Integer> s = new Stack<>();
        int n = height.length;
        int sum =0;
        for(int i =0;i<n;i++){
            while(!s.isEmpty()&&height[s.peek()]<height[i]){
                int top = s.pop();
                if(s.isEmpty())break;
                int left=s.peek();
                int newHeight= Math.min(height[i],height[left])-height[top];
                int distence = i - left-1;
                sum+=newHeight*distence;
            }
            s.push(i);
        }
        return sum;
    }
}

最后动态规划反而快一点。

之前想到的从最大值向两边扩散反而是动态规划的一种，因为划分出去之后条件复杂了很多，容易出错。