题目描述
给定 $n$ 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。感谢 Marcos 贡献此图。
样例
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
算法1
(单调栈) $O(n)$
这道题的关键在于如何将水的面积分解,我们可以分层来算,可以观察到每层水都是由一个U
型构成的,对于每层水我们需要计算它的宽度和高度,这个可以利用单调栈来计算。
对每个方柱我们找到右边第一个大于它的柱子,在左边找到第一个大于等于它的柱子,这两个柱子之间的距离(即宽度)乘以他们中最小值和当前柱子的差(即高度)就是当前柱子能装水的数量(这一层水的面积)。维护一个单调递减的栈(非严格单调,可以有相同的值),对每个柱子统计就可得出答案。
注意对于相同高度的柱子即同一层的柱子,只会有最左边的柱子会被统计到,相当于每层只算了一次,不会重复计算。
另外对称的,我们也可以用一个非严格单调递减的栈对每个方柱找到右边第一个大于等于它的柱子,在左边找到第一个大于它的柱子,这样相同高度的柱子只有最右边的柱子会被统计到。这只需要将代码中的height[stk.top()] < height[i]
改成height[stk.top()] <= height[i]
即可。
C++ 代码
class Solution {
public:
int trap(vector<int>& height) {
stack<int> stk;
int res = 0;
for (int i = 0; i < height.size(); i ++ )
{
while (!stk.empty() && height[stk.top()] < height[i])
{
int t = stk.top();
stk.pop();
if (stk.empty()) break;
int len = i - stk.top() - 1;
int h = min(height[stk.top()], height[i]) - height[t];
res += h * len;
}
stk.push(i);
}
return res;
}
};
算法2
(双指针) $O(n)$
我们也可以用另一种方式来将水的面积进行分解,我们可以计算每个柱子上能装多少水,换句话说就是对于每个柱子找到左边和右边的最大高度,这两个的最小值减去当前柱子的高度就是该柱子的盛水量。
计算每个点左右两边的最大值可以分别开一个数组然后简单的遍历一遍就得到,不过这样会扫描数组三遍,其实还有一种更巧妙的方法即用双指针来做:
我们从从头尾维护两个指针分别开始扫描,每个指针维护当前遇到的最大值,每次比较头尾的最大值,如果左边较小说明下一个点存的水取决于左边,这是因为首先左边的最大值已经统计完了,虽然右边还有未扫描到的值但该值无论大于小于或者等于当前右指针的值都不会影响答案的计算,同理可得如果右边较小则取决于右边。
可以把两个指针想象成边界,当边界之间没有柱子的时候结束循环。
C++ 代码
class Solution {
public:
int trap(vector<int>& height) {
if (height.size() < 3) return 0;
int l = 0, r = height.size() - 1;
int l_max = height[l], r_max = height[r];
int res = 0;
while (l < r - 1)
{
if (height[l] < height[r])
{
l ++ ;
int w = l_max - height[l];
if (w > 0) res += w;
l_max = max(l_max, height[l]);
}
else
{
r -- ;
int w = r_max - height[r];
if (w > 0) res += w;
r_max = max(r_max, height[r]);
}
}
return res;
}
};
算法3
(单调栈) $O(n)$
图片来自yxc:
同样是按照分层计算的思路,我们对于每层水可以按照它的左边界来算。如图所示红色部分的水已经被计算过了,现在新来了一个柱子我们要计算黄色部分的面积。那么可以观察到从第二个栈顶 (它是第一层水的左边界) 开始,每层水的数量等于宽度乘高度,高度就是当前栈顶的高度减去上一个栈顶的高度,宽度就是当前柱子的下标与当前要入栈的柱子的下标间的距离。另外把当前柱子压入栈中的时候还有一层水要算,这里宽度就是当前要入栈的柱子的高度与上一个栈顶高度的差。
注意这里对于连续的高度相同的柱子而言,我们是用最右边的柱子来统计答案的。
总结起来大体上是要在维护单调栈的过程中另外维护一些状态,这里是上一个栈顶的高度level
以及更新答案res
。
C++ 代码
Class Solution {
public:
int trap(vector<int>& height) {
stack<int> stk;
int res = 0;
for (int i = 0; i < height.size(); i ++ ) {
int level = 0;
while (stk.size() && height[stk.top()] <= height[i]) {
res += (i - stk.top() - 1) * (height[stk.top()] - level);
level = height[stk.top()];
stk.pop();
}
if (stk.size()) {
res += (i - stk.top() - 1) * (height[i] - level);
}
stk.push(i);
}
return res;
}
};
总结与思考
关于单调栈的应用有很多,它主要的作用是可以找到某个元素左边或右边第一个大于或小于它的元素。举例来说用一个严格单调递增的栈从左往右扫描一遍就可以得到每个元素左边第一个小于它的元素,同时也可以得到右边第一个小于等于它的元素。原因是当一个元素入栈的时候,对栈里所有大于等于它的元素而言,它就是它们右边第一个小于等于它们的元素,而当这个元素可以入栈时,栈顶的元素就是该元素左边第一个小于它的元素。
同理我们用非严格单调递增的栈则可以得到每个元素左边第一个小于等于它的元素已经右边第一个小于它的元素。
类似的对单调递减的栈我们也可以得到对称的结论。所以具体该采用哪种栈需要结合具体题目的性质来分析,看我们需要找到第一个大于/小于/大于等于/小于等于的元素。
讲的非常透彻