题目描述

给定 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

样例

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

算法1

(暴力枚举)

每个i柱子雨水的储量就是：从最左边到这跟柱子(包括这根柱子)的最大值l_max，和从最右边到这跟柱子（包括这根柱子）的最大值r_max两个值的最小值min(l_max, r_max)再减去height[i]
所以暴力算法就是在遍历数组过程中遍历i的两端获取l_max和r_max然后计算雨水的储量。

时间复杂度

这样做每次遍历一个元素都需要从头到i和从尾到i遍历一遍链表，所以时间复杂度是:$O(n^2)$

C++ 代码

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size(), ans = 0;
        for(int i =0; i<n; i++){
            int l, r, l_max, r_max;
            l_max = r_max = INT_MIN;
            for(int l = 0; l <= i; l++) l_max = max(l_max, height[l]);
            for(int r = n - 1; r>=i; r--) r_max = max(r_max, height[r]);
            ans += min(l_max, r_max) - height[i];
        }
        return ans;
    }
};

算法2

递推 $O(n)$

从上面的算法可以看出来，我们只需要用两个数组将每个i对应的l_max和r_max存储起来，然后在遍历的过程中查询、计算即可，所以我们创建数组f用于存储从0~i（包括i）数组中的最大值和数组g用于存储从i~n-1（包括n-1）数组中的最大值。

时间复杂度

可以看出来，我们需要先遍历两次数组创建f和g，然后再遍历一次进行雨水储量的计算。总共遍历三次，所以时间复杂度是O(n)
代价是空间复杂度为O(n)

C++ 代码

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> f(n + 1), g(n + 2);
        //f和g从1开始，方便处理边界，g设为n+2也是这个目的。
        for(int i = 1; i <= n; i++) f[i] = max(f[i - 1], height[i - 1]);
        for(int i = n; i > 0; i--) g[i] = max(g[i + 1], height[i - 1]);
        int ans = 0;
        for(int i = 0; i<n; i++){
            ans += min(f[i + 1], g[i + 1]) - height[i];
        }
        return ans;
    }
};

算法3

双指针算法 $O(n)$

通过上面两个算法我们可以看出，一个格子的储水量，是由l_max和r_max较小的一方决定的。
所以我们可以设置两个指针l和r分别从头向尾和从尾向头部遍历，并且用l_max和r_max记录遍历过的元素的最大值。注意，这里的l_max和r_max和之前的是不同的，l_max是从0~l中元素的最大值，相当于l指针左边的元素的最大值（包括l）。反之r_max则是r指针右边的元素的最大值（包括r）。
那么我们可以看到，当l遍历到第k个位置的时候：

第一种情况：

如果l_max < r_max，又因为l右侧的所有元素（包括l）的最大值是大于等于r_max的（因为从l~r可能有元素大于r_max）,那么也就说明指针l左侧的最大值是小于l右侧的最大值的，所以就可以直接用l_max计算出l指向的位置的储水量。

第二种情况：

同样的，如果l_max >= r_max，也就说明r左侧的元素的最大值是大于等于r_max的，所以说我们也可以直接使用r_max来计算r元素指向的所有最大值。
这样我们就可以看到当遍历l和r的过程中，我们就可以直接计算出总的储水量。

时间复杂度

l和r只遍历了一遍数组，所以时间复杂度是$O(n)$

代码

class Solution {
public:
    int trap(vector<int>& height) {
        if(!height.size()) return 0;
        int l_max, r_max, l, r;
        l = 0, l_max = height[l];
        r = height.size() - 1, r_max = height[r];

        int ans = 0;
        while(l < r){
            if(l_max < r_max){
                ans += l_max - height[l];
                l++;
                l_max = max(l_max, height[l]);
            }
            else{
                ans += r_max - height[r];
                r--;
                r_max = max(r_max, height[r]);
            }
        }
        return ans;
    }
};