LeetCode(042)-Trapping Rain Water (O(N))

题目：

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

翻译：

使用两根指针：给定 n 个非负整数表示每个宽度为1的柱子的高度图，计算下雨之后能接多少水。给定 n 个非负整数表示每个宽度为1的柱子的高度图，计算下雨之后能接多少水。
例如，
输入 [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 个单位的雨水（蓝色部分）。

方法一：采用两根指针，数组记录一边峰高

实现复杂度：O(n);

1. 一根从右往左，使用数组记录此处每个坐标的最大峰值。
2. 一根从左往右遍历。更新位置i左边的峰值，并且计算积水多少。
3. 水面高度取两个峰值的最小值。积水值最小为0。

class Solution {
    public int trap(int[] height) {
        if(height==null || height.length<=1){
            return 0;
        }
        int num=0;
        int maxL=height[0];
        int maxR=0;
        int[] numMaxR=new int [height.length];
        //找出从右边数每个角标得最大值
        for(int i=height.length-1 ; i>=0; i--){
            if(height[i]>maxR){
                numMaxR[i]=maxR=height[i];
            }else{
                numMaxR[i]=maxR;
            }
        }
        //注意，最外面两个坐标不能计算
        for(int j=1 ;j<height.length-1 ;j++){
            if(height[j]>maxL){
                maxL=height[j];
            }
            int n=Math.min(numMaxR[j],maxL)-height[j];//每个坐标净水高
            num+=Math.max(n,0); //防止n小于0;
        }
        return num;
    }
}

方法二：采用单调栈；

单调栈的一个优势就是线程时间复杂度 ，所有的元素只会进栈一次，而且出栈后不再进来。
单调递增栈可以找到左起第一个比当前数字小的元素。
单调递减栈可以找到左起第一个比当前元素大的元素。

思路：

只有两边高中间低时，才可以装水。我们对低洼的地方感兴趣，那么就一个使用单调递减栈 ，将递减的边界存进去，一旦发现当前的数字大于栈顶元素，那么就可能会有装水的地方(可能是因为如果当前位置是坐标第二个位置，那么是不会有装水的地方) 。当前数字就是右边界 ，我们从占中至少需要取出两个数字，才可以形成一个洼漕。先取出的那个最小(中间)的数字就是坑槽的最低点，在取出的数字就是左边界 ，我们比较左右边界，取其中较小的值为装水的边界，然后用次高度减去水槽最低点的高度，乘以左右边界的距离就是装水量。由于需要知道左右边界的位置，所以维护的是递减栈，但是栈中数字并不是递减的高度 ，而是递减的高度的坐标。

代码实现：

class Solution {
    public int trap(int[] height) {
        if(height==null || height.length<=1){
            return 0;
        }
        Stack<Integer> s=new Stack(); //栈
        int num=0;
        for(int i=0; i<height.length; i++) {
            //如果栈为空或者栈顶元素高度大于当前元素高度
           if(s.empty()==true || height[i]<height[s.peek()]){
               s.push(i);
           }else{
               //当栈不为空，并且栈顶元素低于右边界
               while(s.empty()==false&&height[i]>height[s.peek()]){
                   int n=s.pop();//求该高度以上 l-i的积水，
                   //找到左边界。
                   if(s.empty()==false){
                       int l=s.peek(); //左边界
                       int low=Math.min(height[i],height[l]); //左右边界低点
                       num+=Math.max(low-height[n],0)*(i-l-1);
                       // n点高度置左右低点存的水
                   }
               }
               s.push(i); //将右边界压入栈中。
           }
        }
        return num;
    }
}