42. 接雨水

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例： 
输入：height = [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 个单位的雨水（蓝色部分表示雨水）。 

提示：
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

思路：
要想知道一个柱子上面能不能装水，那就需要知道左右两个方向有没有两根比自己高的柱子；如果知道这个就不难解决问题；那么怎么知道其左边最大值呢 ？需要用到动态规划思想 只需要知道当前位置前一个的左边最大值 跟 前一个位置的值 做对比就可以了！

时间复杂度：O(n)
空间复杂度：O(n)

class Solution {
    public int trap(int[] height) {
      
      if(height==null||height.length==0) return 0;
      
      int lastIdx = height.length - 2;
      
      int[] leftMaxs = new int[height.length];
      int[] rightMaxs = new int[height.length];
      //求出i位置左边最大值和右边最大值
      for(int i = 1;i<=lastIdx;i++){
          leftMaxs[i] = Math.max(leftMaxs[i-1],height[i-1]);
      }

      for(int i = lastIdx;i >= 1;i--){
          rightMaxs[i] = Math.max(rightMaxs[i+1],height[i+1]);
      }
       
       int water = 0;

       for(int i = 1;i <= lastIdx;i++) {
           //找到左右两边最大中较小的哪一个
           int min = Math.min(leftMaxs[i],rightMaxs[i]);
           int currH = height[i];
           //当前高度大于等于左右两边最小高度，没法存水 直接跳过
           if(min <= currH) continue;
           //来到这里说明当前柱子可以存水
           water = water + (min - currH);
       }

       return water;

    }
}

优化：还是对比当前高度左右的最大高度的逻辑，只不过不需要再专门去求出左右两边的数组；而是通过l++ 和 r-- 来处理；因为如果 L 需要++，那就说明右边一定是有一个数大于左边的，那么目前得到的最大值跟当前值对比后得到的最大值，就是两边最大值中的最小值，用最小值减去当前值就得出 当前柱子能接多少单位的水咯 ！

核心逻辑：每次只移动那个相对小的 大的不动， 只要确定一边的最大值量边有比这个值大就行，此时已经确定的最大值就可以用来计算装水量了

时间复杂度：O(n)
空间复杂度：O(1)

class Solution {
    
    public int trap(int[] height) {
      
      if(height==null||height.length==0) return 0;
      
      int l = 0;
      int r = height.length - 1;
      int lowerMax = 0;//左边或右边最大值
      int water = 0;

      while(l < r) {

         //左右两边较小的高度
         int lower = height[height[l]<=height[r]?l++:r--];
         //目前为止遇到的最大lower
         lowerMax = Math.max(lowerMax,lower);
         //结果
         water = water + (lowerMax - lower);//lowerMax - lower 的值就是能放的水，这是规律

      }

      return water;
    }
}