interviewalgo
, , , , ,
Source
Edit
History

42. 接雨水

Introduction

Question：42. 接雨水

解法一

Analysis

这道题有挺多中解法的，这里写的是早上突然灵光一闪想到的（之前看过这道题目，但是没思路就没做）。然后直接一次AC了。

大概的想法是，雨水只可能从两边流失，所以通过简单的推算，我们可以得到下面这条公式：

（柱子个数 X 柱子最高高度）= 柱子面积 + 左边流失面积 + 右边流失面积 + 接到雨水面积。

通过上面这个问题，就把问题转变成求解左边流失面积。

从左向右遍历，只有当柱子的最高高度产生变化时，左边流失面积才会增加，而增加的大小为 当前遍历长度 X 高度变化差。

求解得到左边流失面积后，只需要转变一下即可得到右边流失面积。

Implement

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int trap(vector<int>& height) {
    // len * max - sum - left - right
    int max = 0;
    int sum = 0;
    int left = 0;
    for(int i = 0;i < height.size(); i++) {
        sum += height[i];
        if (height[i] > max) {
            left += (height[i] - max) * i;
            max = height[i];
        }
    }
    int right = 0;
    int tempmax = 0;
    for(int i = height.size()-1;tempmax < max; i--) {
        if (height[i] > tempmax) {
            right += (height[i] - tempmax) * (height.size()-1 - i);
            tempmax = height[i];
        }
    }
    return height.size() * max - sum - left - right;
}