算法--接雨水问题

一想又好久没更新文章了。唉，初次体验到一种像是被人赶稿的感觉。。。不过既然决定要写博客就一定要坚持下去。。。。。所以今天写点啥呢。。。要不就写一个简单点的算法吧。。。于是就找到了这道题。。。（为啥要打这么多’。'呢。。。欸好像又下意识的打出来了）
所以不说废话了进入正题👇

Leetcode-42接雨水问题

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

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/trapping-rain-water

那一看到题干，脑子里必然本源的想到一种暴力方法，从左往右扫描，记录位差。

• 从左面第一个非零的开始记录，第一个是1，然后往右扫描。
• 遇到比这个记录点大的点位更新记录点
• 计算两点之间的差
• 说的比较含糊，且表述可能还有点不正确，不过问题不大，这里面涉及到很多情况，简单来讲暴力方案一般不采取。。。

所以呢思考一下正确解法
实力有限所以采用官方题解的图

• 从左扫描一次（左上图），再从右扫描一次（右上图）
• 计算出整个左加右的大小（下图）称为总大小
• 我们把原来的大小称为原大小，即题干图里面的黑色部分（数组累加）
• 我们用总大小-原大小-重合部分（下图虚线部分）即为所求
• 这样的时间复杂度为O（n）

附上java代码

public class Solution {

    public int Max(int a,int b){
        return a>b?a:b;
    }

    public int trap(int[] height) {
    //注意这个空数组是个坑
        if (height.length<=0)
            return 0;
        int[] left = new int[height.length];
        int[] right = new int[height.length];
        int height_sum = height[0];
        //重合部分
        int sum = 0;
        //总大小
        int max_sum;
        //一个标记用于计算总大小
        //总大小等于数组长度*数组中最大的元素
        int max_flag;
        left[0] = height[0];
        right[height.length-1] = height[height.length-1];
        max_flag = height[0];
        //左扫描的同时计算总大小，同时计算数组的累加
        for (int i = 1 ; i < height.length; i++) {
            height_sum+= height[i];
            if (max_flag<height[i])
                max_flag = height[i];
            left[i] = Max(height[i],left[i-1]);
        }
        //计算总大小
        max_sum = max_flag*height.length;
        //右扫描
        for (int i = height.length-2; i >=0 ; i--) {
            right[i] = Max(height[i],right[i+1]);
        }
        //计算重合部分
        for (int i = 0; i < height.length; i++) {
            sum+= Math.abs(left[i]-right[i]);
        }
        return max_sum - sum - height_sum;
    }
}

以上