0%

42.接雨水

42.接雨水

题目描述:

给出 $n$ 个非负整数表示每个宽度为 $1$ 的柱子的高度图,计算按照此排列的柱子,能够接多少雨水。

数据范围:
$1\le n \le 2\times 10^4$

题解:

单调栈:

使用单调栈,维护一个单调减的栈,如果遇到更高的柱子则出栈求贡献,栈内需要存下标,一般存下标比较通用性比较好。出栈求贡献之后需要更新当前液面的高度,以方便下次求贡献。当出栈完毕时需要检查栈是否为空,不为空时需要加上新的贡献。

动态规划:

对于每一个高度 $height[i]$ 需要找出左右两侧的最大高度,然后就可以得到该列的贡献。每次遍历的话复杂度是 $O(n^2)$ ,可以使用动态规划维护这个高度,有点类似悬线法。

双指针

由于动态规划数组实际只用到了一个元素,考虑使用双指针优化。使用两个变量 $leftMax, rightMax$ 替换数组,同时使用双指针 $left,right$ 滑动更新 。

  • $leftMax\lt rightMax$ 说明当前位置的贡献为 $leftMax-height[l]$
  • $leftMax >= rightMax$ 当前位置的贡献为 $rightMax - height[r]$

因为只要左右两侧有更高的,就会存在贡献。而 $leftMax \ge height[l|r], rightMax \ge height[l|r]$ ,因此左右两侧不存在更高的柱子的情况也不受到影响。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
static void optimize_cpp_stdio() { ios::sync_with_stdio(false), cin.tie(0); }
// 维护单调递减栈
stack<int> st;
int trap(vector<int> &height)
{
optimize_cpp_stdio();
int n = height.size();
int ans = 0;
for (int i = 0; i < n; ++i)
{
int pre = 0;
while (st.size() && height[st.top()] <= height[i])
{

ans += (height[st.top()] - pre) * (i - st.top() - 1);
pre = height[st.top()];
st.pop();
}
if (st.size())
ans += (height[i] - pre) * (i - st.top() - 1);
st.push(i);
// cout << i << ", " << ans << endl;
}

return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
static void optimize_cpp_stdio() { ios::sync_with_stdio(false), cin.tie(0); }
int trap(vector<int> &height)
{
optimize_cpp_stdio();
int n = height.size();
int l, r, lm, rm;
l = 0, r = n - 1;
lm = rm = 0;
int ans = 0;
while (l < r)
{
lm = max(height[l], lm);
rm = max(height[r], rm);
if (lm < rm)
ans += lm - height[l++];
else
ans += rm - height[r--];
}
return ans;
}
};