每日一言

今天总算是把接雨水看明白了（应该吧） 本来以为今天也写不了 但没想到写出来了
真的有一种茅塞顿开的感觉

42.接雨水

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

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

输入：height = [4,2,0,3,2,5]
输出：9

提示：

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

class Solution {
    public int trap(int[] height) {
        //初始化答案为0
        int ans=0;

        //定义前缀高度的最大值
        int preMax=0;

        //定义后缀高度的最大值
        int sufMax=0;

        //左指针指向数组第一个元素
        int left=0;

        //右指针指向数组最后一个元素
        int right=height.length-1;

        //当左右指针不重合时
        while(left<right){
            //更新前缀的最大值
            preMax=Math.max(preMax,height[left]);

            //更新后缀的最大值
            sufMax=Math.max(sufMax,height[right]);

            //当前缀最大值小于后缀最大值时
            if(preMax<sufMax){
                //答案更新
                ans+=preMax-height[left];

                //左指针右移
                left++;
            }else{
                ans+=sufMax-height[right];
                right--;
            }
        }
        return ans;
    }
}

解释（个人理解）：
于其叫做前缀最大值 后缀最大值 我觉的叫接水板和挡水板更加好理解
前缀最大值 后缀最大值 那个更小乃个就是接水板
为什么

if(preMax<sufMax){
                //答案更新
                ans+=preMax-height[left];

                //左指针右移
                left++;
            }else{
                ans+=sufMax-height[right];
                right--;

就要更新答案呢 我昨天就一直被这个问题困扰
就以图片为例 假设这时preMax=1 sufMax=3 我们假设两个中间没有任何的方块
那么我们高度为一的方块旁边 是不是也可以接到水啊 也就是说只要挡水板大于等于接水板 就可以接到水

转载自CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/gzh070923/article/details/158893452