Trapping Rain Water

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.

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

直接做法

从左边往右边扫描，记录左边的最高值， 从右边往左扫描，记录右边的最大值 再次扫描，去某个点左边与右边的最低值，如果该值大于当前bar的高度，那么这个bar顶上就能储存水

public class Solution {
    public int trap(int[] A) {
        if (A == null) {
            return 0;
        }

        int max = 0;

        int len = A.length;
        int[] left = new int[len];
        int[] right = new int[len];

        // count the highest bar from the left to the current.
        for (int i = 0; i < len; i++) {
            left[i] = i == 0 ? A[i]: Math.max(left[i - 1], A[i]);
        }

        // count the highest bar from right to current.
        for (int i = len - 1; i >= 0; i--) {
            right[i] = i == len - 1 ? A[i]: Math.max(right[i + 1], A[i]);
        }

        // count the largest water which can contain.
        for (int i = 0; i < len; i++) {
            int height = Math.min(right[i], left[i]);
            if (height > A[i]) {
                max += height - A[i];
            }
        }

        return max;
    }
}

2019 递减stack

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) return 0;
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        for (int i = 0; i < height.length; i++) {
            while(!stack.isEmpty() && height[stack.peek()] < height[i]) {
                int right = height[i];
                int cur = stack.pop();
                int left = stack.isEmpty() ? height[cur]: height[stack.peek()];
                int diff = Math.min(right, left);
                int leftIndex = stack.isEmpty() ? cur : stack.peek();
                int width = i - leftIndex - 1;
                res += width * (diff - height[cur]);
            }
            stack.push(i);
        }
        return res;
    }
}

public class Solution {
    /**
     * @param heights: an array of integers
     * @return: a integer
     */
    public int trap(int[] heights) {
        if(heights == null || heights.length == 0) return 0;
        int start = 0;
        int end = heights.length - 1;
        int leftHeight = heights[start];
        int righHeight = heights[end];
        int res = 0;
        while(start < end){
            if(heights[start] < heights[end]){
                start++;
                if(heights[start] < leftHeight){
                    res = res + leftHeight - heights[start];
                    continue;
                }else{
                    leftHeight = heights[start];
                }
            }else{
                end--;
                if(heights[end] < righHeight){
                    res = res + righHeight - heights[end];
                    continue;
                }else{
                    righHeight = heights[end];
                }

            }
        }
        return res;
    }
}

自己的想法：先找出看两遍那边最小，然后从这边开始如果比开始变小的话，就可以一直算，知道拿刀一边和起始边一样了，那么要重新开始新一轮的比较了

 public int trap(int[] heights) {

     if(heights == null || heights.length == 0) return 0;

     int start = 0;

     int end = heights.length - 1;

     int leftHeight = heights[start];

     int righHeight = heights[end];

     int res = 0;

     while(start < end){

         if(heights[start] < heights[end]){

             leftHeight = heights[start];

             start++;        

                while(heights[start] < leftHeight && start < end){

                     res = res + leftHeight - heights[start];

                     start++;

                 }



         }else{

             righHeight = heights[end];

                end--;

             while(heights[end] < righHeight && start < end){

                 res = res + righHeight - heights[end];

                  end--;

             }

         }

         }

         return res;

 }