题目解析

给出一个数组，里面的数字表示柱状体的高度，需要求出柱状体围绕能够存多少雨水，比如下面的例子

1
2
3
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
因为(1,0,2)能够存面积1的水，(2,1,0,1,3)能存下面积4的水，(2,1,2)能存下1的水

举个🌰

方法一 暴力求解

这道题的对于水的面积综合，可以看成每个元素i在它之上能够存多少水，这取决于两个边界，左右两个最大高度L、R，然后元素i能够存的水面积，等于min(L, R) - height[i]。
时间复杂度O(n^2)，耗时308ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int trap(vector<int>& height) {
        int result = 0;
        for (int i = 0; i < height.size(); i++) {
            int L = 0, R = 0;
            for (int j = i; j >= 0; j--) {
                L = max(height[j], L);
            }
            for (int j = i; j < height.size(); j++) {
                R = max(height[j], R);
            }
            result += min(L, R) - height[i];
        }
        return result;
    }
};

方法二 记忆存储

因为在每一次i都需要寻找L，R，做了很多重复的工作，其实可以把它们放在数组里，使用时查询即可。
时间复杂度O(n), 12ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int trap(vector<int>& height) {
        int result = 0;
        vector<int> Ls, Rs;
        int maxTemp = 0;
        for (int i = 0; i < height.size(); i++) {
            maxTemp = max(maxTemp, height[i]);
            Ls.push_back(maxTemp);
        }
        maxTemp = 0;
        for (int i = height.size()-1; i >= 0; i--) {
            maxTemp = max(maxTemp, height[i]);
            Rs.push_back(maxTemp);
        }
        reverse(begin(Rs), end(Rs));
        for (int i = 0; i < height.size(); i++) {
            result += min(Rs[i], Ls[i]) - height[i];
        }
        return result;
    }
};

关键在前两个for循环中，第一个循环维持从i节点往左看的最大值，每次都把最大值放入数组中，之后就不需要再遍历。
第二个循环维持在i位置往右看的最高值，因为是push_back与实际顺序相反，后面需要再次翻转数组。