收集雨水

class Solution {
public:
    int trap(int heights[], int n) {
        int maxhigh=0;
        int left=0,right=0;
        for(int i=0;i<n;i++)//找到最大值的下标
        {
            if(heights[i]>heights[maxhigh])
                maxhigh=i;
        }
        int sum=0;
        for(int i=0;i<maxhigh;i++)//计算左边的容量
        {
            if(heights[i]<left)
               sum+=(left-heights[i]);
            else
               left=heights[i];
        }
        
        for(int j=n-1;j>maxhigh;j--)//计算右边的容量
        {
            if(heights[j]<right)
               sum+=(right-heights[j]);
            else
               right=heights[j];
        }
        return sum;
    }
};

    int trap(int A[], int n) {
        stack<int> s;
        int res=0;
        for(int i=0;i<n;i++)
        {     
                 /*
                    如果新的高度比保存的s.top()高，证明找到右边界，可以计算，此处应为while
                    因为一次只能处理一层，如 2 1 0 2 ，先处理1 0 2 部分 填充1，然后继续计算2112计算2 
           */ while(!s.empty() && A[s.top()]<A[i])  
            {
                int t =s.top();
                s.pop();
                while(!s.empty() && A[s.top()]<=A[t])
                        s.pop();
                if(!s.empty())
                    res+= (std::min(A[s.top()],A[i])-A[t])*(i-s.top()-1);
            }
            s.push(i);
        }
        return res;
    }

class Solution {
public:
	int trap(int A[], int n) {
		if (n <= 2) return 0;
		int lefttop = A[0], righttop = A[n - 1];
		int i = 1, j = n - 2;
		int sums = 0;
		while (i <= j) {
			if (lefttop > righttop) {
				sums += max(0, righttop - A[j]);
				righttop = max(righttop, A[j]);
				--j;
			}
			else {
				sums += max(0, lefttop - A[i]);
				lefttop = max(lefttop, A[i]);
				++i;
			}
		}
		return sums;
	}
};

public class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0){
            return 0;
        }
        int max = 0;
        int v = 0;
        int[] container = new int[height.length];
        for (int i = 0; i < height.length; i++) {
            container[i] = max;
            max = Math.max(max, height[i]);
        }
        max = 0;
        for (int i = height.length - 1; i >= 0; i--) {
            container[i] = Math.min(max, container[i]);
            max = Math.max(max, height[i]);
            v += container[i] - height[i] > 0 ? container[i] - height[i] : 0;
        }

        return v;

    }
}

	运行时间：5ms



	占用内存：612k

//简单暴力的方法:一层一层的算,比如所给例子中第一层有2个坑,第二层有4个坑,一共有6个坑
//关键就是怎么把序列转成一层层,可以这样转:
//{0,1,0,2,1,0,1,3,2,1,2,1}
//第一层:遍历元素>=1的都为1,<1的为0,{0,1,0,1,1,0,1,1,1,1,1,1}调用cal算坑数
//第二层:遍历元素>=2的都为1,<2的为0,{0,0,0,1,0,0,0,1,1,0,1,0}调用cal算坑数
//第三层:遍历元素>=3的都为1,<3的为0,{0,0,0,0,0,0,0,1,0,0,0,0} 
class Solution 
public:
    int cal(int B[],int n)
    {   int j=0,sum=0;
        bool flag=true;
        for(int i=0;i<n;i++)
        {
            if(B[i]==1 && flag){ j=i; flag=false;}
            else if(B[i]==1 && !flag) {sum+=i-j-1; flag=true; i--;}
        }
        return sum;
    }
    int trap(int A[], int n) {
        
        int MAX=0;
        for(int i=0;i<n;i++)//找层数
        {
            if(A[i]>MAX) MAX=A[i];
        }
        int B[n];
        int res=0;
        for(int i=1;i<=MAX;i++)
        {
            for(int j=0;j<n;j++)
            {
                
                if(A[j]>=i) B[j]=1;
                else B[j]=0;
            }
            res+=cal(B,n);
            
        }
        return res;
    }
};

磕磕绊绊写出来了...再碰上的话写出来也难

import java.util.Stack;

public class Solution {
    public int trap(int[] A) {
        int len = A.length;
        Stack<Integer> stack = new Stack<>();
        int trap = 0;
        for (int i = 0; i < len; i++) {
            int hCur = A[i];
            int hPre = stack.empty() ? 0 : A[stack.peek()];
            if (hCur > hPre && !stack.empty()) {
                hPre = A[stack.pop()];
                int left = stack.empty() ? 0 : stack.peek();
                int distance;
                if (A[left] > hCur) {
                    distance = hCur - hPre;
                } else {
                    if (stack.size() == 1) {
                        stack.pop();
                    }
                    distance = A[left] - hPre;
                }
                 if (distance > 0) {
                     trap = trap + distance * (i - left - 1);
                 }
                i--;
            } else if (hCur == hPre && !stack.empty()) {
                stack.pop();
                stack.push(i);
            } else {
                stack.push(i);
            }
        }
        return trap;
    }
}

class Solution {
public:
    int trap(int A[], int n) {
        int left=0,right=0,sum=0,maxhight=0,k=0;
        for(int i=0;i<n;i++){       //找到数组中最高的高度
            if(A[i]>maxhight){
                maxhight=A[i];
                k=i;
            }
        }
        for(int i=0;i<k;i++){       //计算最高高度位置左边的水容量大小
            if(A[i]<left)sum+=(left-A[i]);
            else left=A[i];
        }
        for(int i=n-1;i>k;i--){      //计算最高高度位置右边的水容量大小
            if(A[i]<right)sum+=(right-A[i]);
            else right=A[i];
        }
        return sum;
    }
};

import java.util.*;


public class Solution {
    /**
     * 
     * @param A int整型一维数组 
     * @return int整型
     */
    public int trap (int[] A) {
        //寻找高度最高值的下标
        int maxIndex = 0;
        for(int i = 0; i < A.length; i++){
            if(A[i] > A[maxIndex]){
                maxIndex = i;
            }
        }
        int sum = 0;
        //计算最高值的左边储水量
        int left = 0;
        for(int i = 0; i < maxIndex; i++){
            if(A[left] > A[i]){
                sum += A[left] - A[i];
            }else{
                left = i;
            }
        }
        //计算最高值右边储水量
        int right = A.length - 1;
        for(int i = A.length - 1; i >= maxIndex; i--){
            if(A[right] > A[i]){
                sum += A[right] - A[i];
            }else{
                right = i;
            }
        }
        return sum;
    }
}

看我看我！！
我们可以一层一层的解决问题，从第一次开始，将大于零的都变成1，则两个1之间夹着的0的个数就是这一层的积水量。
然后去掉这一次，检查上面一层。


int trap(int A[], int n) {
        int *B=new int [n];
        int sum=0;//总积水量
        while(true){
            int location=-1;
            for(int i=0;i<n;i++){
                if(A[i]==0)B[i]=0;//如果是0，不变
                else{
                    B[i]=1;//如果是正数，变成1
                    if(location>=0)sum+=i-location-1;//location是1的位置
                    location=i;
                    A[i]-=1;//原来的数组都减去这一层高度
                }
            }
            if(location==-1)break;//如果location是-1证明全都是0了，每一层都检查完毕。
        }
        delete[]B;
        return sum;
    }

 public int trap(int[] A) {
        if(A.length<=2) return 0;
        int lefttop = A[0], righttop = A[A.length-1];
        int i=1, j=A.length-2;
        int sums = 0;
        while(i<=j){
            if(lefttop>righttop){
                if(righttop>=A[j]) sums+= righttop-A[j--];
                else righttop = A[j--];
            }
            else{
                if(lefttop>=A[i]) sums+= lefttop-A[i++];
                else lefttop = A[i++];
            }
        }
        return sums;
    }

leetcode最佳答案
class Solution {
public:
    int trap(int A[], int n) {
        int L_height=0; int r_height=0;
        int f=0, b=n-1;
        int res = 0;
        while(f<=b){
            if(L_height<r_height){
                res +=max(0, (L_height-A[f])) ;
                L_height=max(L_height, A[f]);
                f++;
            }else{
                res += max(0, (r_height-A[b]));
                r_height=max(r_height, A[b]);
                b--;
            }
        }
        return res;
    }
};

class Solution {
public:
    int trap(int A[], int n) {
        int val = 0;
        int i,j;
        bool flag = false;
        for(i=0;i<n;i++)
        {
            for(j=i+1;j<n;j++)
            {
                if(A[j]>A[i])
                    break;
                if(j==n-1 && A[j]<=A[i])
                    flag = true;
            }
            if(flag)
                break;
            for(int k=i+1;k<j;k++)
            {
                val+=A[i]-A[k];
            }
            i=j-1;
        }
        flag = false;
        for(i=n-1;i>=0;i--)
        {
            for(j=i-1;j>=0;j--)
            {
                if(A[j]>=A[i])
                    break;
                if(j==0 && A[j]<A[i])
                    flag = true;
            }
            if(flag)
                break;
            for(int k=i-1;k>j;k--)
            {
                val+=A[i]-A[k];
            }
            i=j+1;
        }
        return val;
    }
};
/*扫描两遍，一次从前往后，一次从后往前，首先找到第一个比起点值大的位置，
记录此位置，计算起点和此位置之间的容积，然后起点设为记录的位置，继续遍历*/

import java.util.*;
public class Solution {
    public int trap(int[] A) {
        int n = A.length;
        int[] maxLeft = new int [n];//找出每个柱子左边最高的
        int[] maxRight = new int [n];//找出每个柱子右边最高的
        
        for(int i=1; i<n; i++){
            maxLeft[i] = Math.max(maxLeft[i-1], A[i-1]);
            maxRight[n-1-i] = Math.max(maxRight[n-i], A[n-i]); 
        }
        
        int sum = 0;
        //从左到右找出每个柱子左右最低的部分，再减去当下柱子本身，得出深度
        for(int i=1; i<n; i++){
            int height = Math.min(maxLeft[i], maxRight[i]);
            if(height > A[i]){
                sum = sum + height - A[i];
            }
        }
        return sum;
    }
}

class Solution {
public:
    int trap(int A[], int n) {
        int l=A[0],r=A[n-1],sum=0;
        int i=1,j=n-2;
        while(i <= j)
        {
        	if(l > r)
        	{
        		sum += max(r-A[j],0);
        		r = max(r,A[j--]);
			}else{
				sum += max(l-A[i],0);
				l = max(l,A[i++]);
			}		
		}
		return sum;
    }
};

class Solution {
public:
    int trap(int A[], int n) {
        int ans=0,l=A[0],r=A[n-1],i=1,j=n-2;
        while(i<=j){
             if(l>r){
                 ans+=max(0,r-A[j]);
                 r=max(r,A[j--]);
             }else {
                 ans+=max(0,l-A[i]);
                 l=max(l,A[i++]);
             }
        }
        return ans;
    }
};

/*
	 * Runtime: 22 ms
	 * 参考自leetcode网友：@yuyibestman 
	 */
	public int trap(int[] height) {
		if (height == null || height.length < 2)
			return 0;
		int leftMax = height[0], rightMax = height[height.length - 1], left = 0, right = height.length - 1;

		int sum = 0;
		while (left < right) {
			leftMax = Math.max(height[left], leftMax);
			rightMax = Math.max(height[right], rightMax);
			if (leftMax < rightMax) {
				sum += leftMax - height[left];
				left++;
			} else {
				sum += rightMax - height[right];
				right--;
			}

		}

		return sum;
	}

	/*
	 * 用总面积减去空白面积，再减去边的面积：分别从两侧从中间搜索，找到最高的边停止 runtime:21ms
	 */
	public int trap_1(int[] height) {
		if (height == null || height.length < 2)
			return 0;
		int max = height[0];
		int sumOfNum = 0;
		// 记录空白面积
		int additionalArea = 0;

		// 找到最高边和所有边的和
		for (int i = 0; i < height.length; i++) {
			if (max < height[i])
				max = height[i];
			sumOfNum += height[i];
		}

		int tmpLarge = height[0];
		int otherEdge = 0;
		// 从左边开始搜索
		for (int i = 0; i < height.length; i++) {
			if (tmpLarge < height[i]) {
				additionalArea += (i - otherEdge) * (max - tmpLarge);
				otherEdge = i;
				tmpLarge = height[i];
			}
			// 找到最高边，停止搜索
			if (height[i] == max)
				break;
		}

		tmpLarge = height[height.length - 1];
		otherEdge = height.length - 1;
		// 从右边开始搜索
		for (int i = height.length - 1; i >= 0; i--) {
			if (tmpLarge < height[i]) {
				additionalArea += (otherEdge - i) * (max - tmpLarge);
				tmpLarge = height[i];
				otherEdge = i;
			}
			// 找到最高边，停止搜索
			if (height[i] == max)
				break;
		}
		int area = height.length * max - sumOfNum - additionalArea;
		return area;
	}