题解 | 接雨水问题

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        // write code here
        LinkedList<Data> stack = new LinkedList<Data>();
        int count =0;
        for (int i = 0; i < arr.length; i++) {
            Data data = new Data(arr[i],i);
            while (!stack.isEmpty() && data.height >  stack.peek().height) {
             Data pop= stack.pop();
             Data left=stack.peek();
             if( left!=null ){
               int width = data.i-left.i-1;
               int height = Math.min(left.height,data.height)-pop.height;
               count += width*height;
              }
            }
            stack.push(data);
        }
        return count;
    }

    static class Data{
        int height;
        int  i;
        public Data(int height,int i){
           this.height =height;
           this.i =i;
        }
    }
}

用单调栈解决，注意细节，不要用一个top指针指向栈顶元素再去比较，不然就一直比较的这个元素，即使是这个元素弹出了这个栈；