[数据结构与算法]★★[leetCode 42] 接雨水 总结

解题思路

这道题有两种主要的思路，一种是按列计算接到的雨水总量，另一种是按行计算接到的雨水总量。

首先来看看如何按列计算雨水总量：

1. 首先，首尾两列肯定是接不到雨水的，不用计算
2. 其次，这一列什么情况下能够接到雨水呢？答案就是，这一列的左右两侧都存在比这一列更高的列，不然的话，这一列肯定是接不到雨水的。仔细想一想就能明白为什么。
3. 如果这一列能够接到雨水，那么这一列的雨水数量是多少？其实就是，取左右两侧最高的列中较低的列，说起来比较拗口，就是取min(maxLeft,maxRight)，用这个高度减去当前列的高度，就是当前列的雨水量
4. 那么按照上述思路，从前往后遍历每一列，对于每一列，计算它这一列的雨水数即可。

代码

public class Solution {
    public int trap(int[] height) {
        int sum=0;
        //第一列和最后一列不用计算
        for (int i=1;i<height.length-1;i++){
        	//依次计算该列左右两侧最高的列
            int l=0,r=0;
            for (int j=i-1;j>=0;j--){
                l=Math.max(l,height[j]);
            }
            for (int k=i+1;k<height.length;k++){
                r=Math.max(r,height[k]);
            }
            //计算雨水
            if (Math.min(l,r)>height[i]){
                sum=sum+Math.min(l,r)-height[i];
            }
        }
        return sum;
    }
}

优化

对于上述思路，时间复杂度是O(n^2)。我们会发现，在每次计算这一列的左右两侧最大高度的时候，出现了重复的计算，导致了时间复杂度的提升。

那么有没有办法优化呢？

有！我们提前把每一列左右两侧的最大高度计算出来，存下来，用的时候直接来拿就好了。
计算这个最大高度的方法，可以用动态规划的思想，这样就可以把时间复杂度优化到O(n)。

思路如下：

1. dp数组的定义，定义maxLeft[i]为第i列左侧的最高高度，maxRight[i]为第i列右侧的最高高度。
2. maxLeft从前往后遍历，maxLeft[i]=MAX(maxLeft[i-1],height[i]),
   maxRight[i]=MAX(maxRight[i+1],height[i])。

其他步骤不变。

代码如下

public class Solution {
    public int trap(int[] height) {
        int[] maxLeft=new int[height.length];
        int[] maxRight=new int[height.length];
        maxLeft[0]=height[0];
        maxRight[height.length-1]=height[height.length-1];
        for (int i=1;i<height.length;i++){
            maxLeft[i]=Math.max(height[i],maxLeft[i-1]);
        }
        for (int j=height.length-2;j>=0;j--){
            maxRight[j]=Math.max(height[j],maxRight[j+1]);
        }
        int sum=0;
        for (int i=1;i<height.length-1;i++){
            int l=maxLeft[i],r=maxRight[i];
            if (Math.min(l,r)>height[i]){
                sum=sum+Math.min(l,r)-height[i];
            }
        }
        return sum;
    }
}

按行计算雨水总量

用单调栈的思想，来依次计算每一行的雨水总量，这个比较不好理解。

我们用一个单调栈来维护目前已经遍历过的列，栈顶到栈底是递减的，当遍历到新的列时，有以下3种情况：

1. height[i]<height[top]，新元素的值小于栈顶的元素值，那么可以把新元素直接加入栈中
2. height[i]==height[top]，新元素的值和栈顶元素一样大，那么更新栈顶元素的下标
3. height[i]>height[top]，新元素的值大于栈顶元素的值，这个栈顶的元素用top来代替，这时说明的top的左右两侧都有比它更高的列，top就是当前能接到雨水的部分的底座。那么当前部分的高度应该是多少呢？其实就是top左右两侧更高的列中较低的那一个，也就是此刻栈中的第二个元素j和当前遍历的元素i中较低的值。
   此时雨水的量就是(i-j-1)*MIN(height[j],height[i]),此时就填上了以top为底座的坑，top弹出。
4. 继续尝试当前遍历的元素能不能压入栈中，重复上述计算，依次计算每一个坑中每一行的雨水量，相当于就是一个填坑的过程。

代码如下

public class Solution {
    public int trap(int[] height) {
        //单调栈
        Deque<Integer> st = new LinkedList<>();
        st.push(0);
        int sum = 0;
        //依次遍历每一列
        for (int i = 1; i < height.length; i++) {
        	//情况1
            if (height[st.peek()] > height[i]) {
                st.push(i);
            } 
            //情况2
            else if (height[st.peek()] == height[i]) {
                st.pop();
                st.push(i);
            } 
            //情况3
            else {
                while (height[st.peek()] < height[i]) {
                    Integer pop = st.pop();
                    if (st.isEmpty()) break;
                    int h = Math.min(height[st.peek()], height[i]) - height[pop];
                    int l = i - st.peek() - 1;
                    sum = sum + h * l;
                }
                st.push(i);
            }
        }
        return sum;
    }
}