理解接雨水算法

一、IDEA注释显示图片

在做题时，需要对照这图片，才能更好的梳理思路。

首先，注释里添加<img/>标签

之后，将鼠标光标放置在需要以阅读模式预览注释的地方，然后按快捷键Ctrl+Alt+Q即可

二、接雨水算法

先看接雨水算法的具体描述

2.1 暴力解法

我做的时候，就对着这个柱状图一直发呆，然后大概发现了思路。

我采取的是分而治之，也就是说，我依次遍历x轴，计算x所在的积水量。积水量=Min(leftMax,rightMax)-height[i]

• leftMax: 表示x<i的height的最大值
• rightMax: 表示x>i的height的最大值

思路有了，上代码。

class Solution {
    public int trap(int[] height) {
        int n = 0;
        for (int i = 0; i < height.length; i++) {
            int max = getMax(height, i);
            int i1 = height[i];
            if (max > i1) {
                n += max - i1;
            }
        }
        return n;
    }

    /**
     * 获取i位置的左右两侧的最大值，取出最大值中的最小值
     */
    public int getMax(int[] height, int i) {
        if (i <= 0 || i >= height.length - 1) {
            return 0;
        }
        int leftMax = -1, rightMax = -1;
        //获取左边最大值
        for (int j = i - 1; j >= 0; j--) {
            int i1 = height[j];
            if (i1 > leftMax) {
                leftMax = i1;
            }
        }
        //获取右边最大值
        for (int j = i + 1; j < height.length; j++) {
            int i1 = height[j];
            if (i1 > rightMax) {
                rightMax = i1;
            }
        }
        return Math.min(leftMax, rightMax);
    }
}

2.2 优化解法

这个做法的时间复杂度是O(n2)，导致后面就超时了。慢就慢在，获取每个下标i最大值时，都需要去循环比较获取。能不能提前将最大值计算出来呢？其实可行的

这里面其实是有规律的，以数组[4,2,0,3,2,5]为例，其对应的每个下标的leftMax和rightMax，如下图。

直接上代码，看代码理解。

class Solution {
    public int trap(int[] height) {
        int n = 0;
        //求出每个位置的左侧最大值
        int[] leftMax = new int[height.length];
        for (int i = 0; i < height.length; i++) {
            if (i == 0) {
                leftMax[i] = 0;
            } else {
                leftMax[i] = Math.max(leftMax[i - 1], height[i - 1]);
            }
        }
        //求出每个位置的右侧最大值
        int[] rightMax = new int[height.length];
        for (int i = height.length - 1; i >= 0; i--) {
            if (i == height.length - 1) {
                rightMax[i] = 0;
            } else {
                rightMax[i] = Math.max(rightMax[i + 1], height[i + 1]);
            }
        }
        //每个位置的左右两侧短板值与当前位置值的差，即当前位置的积水
        for (int i = 0; i < height.length; i++) {
            int min = Math.min(leftMax[i], rightMax[i]);
            int i1 = height[i];
            if (min > i1) {
                n += min - i1;
            }
        }
        return n;
    }
}

时间复杂度为O(n)，太妙了。