42. 接雨水 #
链接 #
题目 #
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5] 输出：9
提示：
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
解答（计算每个位置） #
首先分别计算每个位置的左侧最高和右侧最高墙，然后计算每个位置能够接住的水量，最后将所有位置能够接住的水量相加，得到最终的返回值。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// debug
class Solution {
public:
int trap(vector<int>& height) {
int n = static_cast<int>(height.size());
vector<int> left(n, 0);
vector<int> right(n, 0);
int lfence=0;
int rfence=0;
for(int i = 0; i < n; i++) {
lfence = max(lfence, height[i]);
left[i] = lfence;
}
for(int j = n - 1; j >=0; j--) {
rfence = max(rfence, height[j]);
right[j] = rfence;
}
int ret = 0;
for(int i = 0; i < n; i++) {
ret += min(left[i], right[i]) - height[i];
}
return ret;
}
};
解答（单调递减栈） #
思路详解 #
我们采用单调递减栈。雨水面积的计算通过归纳可以得到。下面介绍思路是怎么想到的：
对照上图。我们依然是先一股脑入栈，然后出栈结算。结算时面积计算原理如下：
- 宽度：取决于当前位置和栈顶下标的距离。例如我们出栈 1 位置的红色矩形时，当前 i=2，栈顶是最左边的矩形，其下标是 0. 因此之间的距离是
i - (0+1) = 1 - 高度：首先，当前位置的高度和栈顶元素的高度，二者取最小值，作为绝对高度。再减去当前元素的高度，得到相对高度。
为什么宽度不是恒定为 1 呢？ 考虑下面的情况。则结算的面积依次是 B 和 A，可以发现宽度是不同的。
代码 #
class Solution {
public:
int trap(vector<int>& heights) {
int trapsum = 0, i = 0;
int n = static_cast<int>(heights.size());
heights.push_back(0);
stack<int> stk;
do {
while (i < n && (stk.empty() || (heights[stk.top()] > heights[i]))) {
stk.push(i++);
}
auto outidx = stk.top();
stk.pop();
auto height = min(stk.empty() ? 0 : heights[stk.top()], heights[i]) -
heights[outidx];
auto width = stk.empty() ? 0 : i - stk.top() - 1;
trapsum += max(height * width, 0);
} while (i < n || !stk.empty());
return trapsum;
}
};
注意事项 #
- 相比于柱状图最大矩形问题，此题注意
while的条件增加了对i < n的限制。 - 当栈空时，取绝对高度为 0
- 高度可能出现负数，因此与 0 做 max。
trapsum += max(height * width, 0)