题目描述

2.PNG
[leetcode42]https://leetcode.com/problems/trapping-rain-water/

思考某一个位置，其能存下水的本质是其左边最大值和右边最大值与当前数的差(值大于0就表明当前位置可以存下水)

思路

那么接下来就有这么几个思路：

1. 在i位置遍历左边右边求左最大和右最大。O(n^2)
2. 使用两个数组，一个数组记录左最大[0，i)，一个数组记录右最大(i,n-1]。遍历两遍即可知道,然后求water[i]即可。O(n)
3. 最最大数组没有必要再求，用一个变量记录左边最大，省去左边这个数组。O(n)
4. （先找到可能的最大值，然后看哪些位置的水可以被算出来）
   5,4，，，3,7 ->4的水量可以确定
   前三种就不贴代码了，看一下方法4

算法四 O(n)time O(1)space

算法步骤

1. 使用四个变量，leftMax：左边最大 rightMax：右边最大 ,两指针left,right。一个变量water记录水量。
2. 两指针开始走，首先看laftMax和rightMax,哪边小，证明哪边就可以结算，处理那边的那个位置的水量，同时更新位置和最值。

代码

public class Solution {
    public int trap(int[] height) {
        if(height==null||height.length<3)
            return 0;
        int leftMax=height[0];
        int rightMax=height[height.length-1];
        int left=1;
        int right=height.length-2;
        int water=0;
        while(left<=right){
            if(leftMax<rightMax){
                water+=Math.max(0,leftMax-height[left]);
                leftMax=Math.max(leftMax,height[left++]);
            }
            else{
                water+=Math.max(0,rightMax-height[right]);
                rightMax=Math.max(rightMax,height[right--]);
            }
        }
        return water;
    }
}

算法五 O(n)time O(1)space

算法步骤

1. 遍历数组，求出最大值所在位置
2. 分别对最大值所在位置的左边和右边求解，求解左边的时候，记录一个左边最大，然后遍历左半部分，如果当前位置小于左最大，那么当前位置可以存水，否则更新左最大。右边同理。

算法原理

为什么可以这么做？因为寻找了最大位置，这个位置的存在就作为了左边和右边的保障，例如对于最大值左边的元素来说，你只需要知道这些元素左边的最大是多少就行了，因为对该位置存水量有限制的就是左边最大，因为他的右边最大就是全局最大，我们拥有这个保障。

代码

    public int trap(int[] height) {
        if(height==null||height.length<3)
            return 0;
        int max=0,maxIndex=0;
        for(int i=0;i<height.length;i++){
            if(height[i]>max)
            {
                max=height[i];
                maxIndex=i;
            }
        }
        int area=0;
        int left=0;
        for(int i=0;i<maxIndex;i++){
            if(height[i]<height[left]){
                area+=height[left]-height[i];
            }
            else
                left=i;
        }
        int right=height.length-1;
       for(int i=height.length-1;i>maxIndex;i--){
           if(height[i]<height[right])
               area+=height[right]-height[i];
           else
               right=i;
       }
        return area;
    }