前言#
今天也是一道困难的题，和前面做的分糖果有一点关系。
题目#
给定 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
分析#
为什么说这道题和前面分糖果有一点关系呢？因为他俩都有一个特点：他们都需要拿到当前元素后面几个
那么根据我们前面总结的规律：如果当前计算需要未来的元素参与，那么我们可以选择预处理，O(2n)它也是O(n)!
不过我们还不能动手，我们还有问题需要解决：怎么才能算出雨水？
你可能会想到通过连续递增/递减区间的方案
右边边界大于等于左边边界，用一个变量存储这期间的凸起
左边界选择最大的，右边界也选择最大的
然后两个边界最小边组成的矩形减去这期间存储的凸起数即是这个区间的雨滴数量但是这个方案其实是有局限的，具体是啥我给忘了。。。。
不如逆向一下，我们一列一列的算，当前列如果比左右两边的矮，那么它就能接收雨水！
不过还有个问题，它可以接收多少雨水？我们并不能直接根据左右两边来计算。
比如[3, 2, 1, 2 , 3]，它可以接收多少雨水是根据左右两个3来计算的
所以我们应该找到这个点左右两边最高的点。
最高？！
最高！
动态规划这不就来了嘛！
那么dp[i]要表示啥？求什么设什么！
你可能第一想法就是设这个接雨水最大的量是多少，不对！
我们的目标是找到相对于当前的左右两个最高点！
那么就存在关系：dp_left[i] = max(dp_left[i - 1], height[i - 1])
然后还有从右边来的dp_right[i] = max(dp_right[i + 1], height[i + 1])
最后，当前元素对应的列可以接收的最多的雨水就是这俩最高点的最低那个（短桶效应） - height[i]
ok，这道题迎刃而解（其实我没做出来，我是看了题解之后写出来的，π_π）
解#
pub fn trap(height: Vec<i32>) -> i32 {
let len = height.len();
if len <= 1 {
return 0;
}
let mut l_dp = vec![0; len];
let mut r_dp = vec![0; len];
l_dp[0] = height[0];
r_dp[len - 1] = height[len - 1];
for i in 1..len {
l_dp[i] = l_dp[i - 1].max(height[i - 1]);
}
for i in (0..=len - 2).rev() {
r_dp[i] = r_dp[i + 1].max(height[i + 1]);
}
let mut count = 0;
for i in 0..len {
let h = height[i];
let min_h = l_dp[i].min(r_dp[i]);
if h < min_h {
count += (min_h - h)
}
}
count
}代码就没啥好说的了
测试用例#
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_trap() {
assert_eq!(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1].to_vec()), 6);
assert_eq!(trap([4, 2, 0, 3, 2, 5].to_vec()), 9);
assert_eq!(trap([5, 4, 1, 2].to_vec()), 1);
assert_eq!(trap([5, 5, 1, 7, 1, 1, 5, 2, 7, 6].to_vec()), 23);
assert_eq!(trap([8, 2, 8, 9, 0, 1, 7, 7, 9].to_vec()), 27);
assert_eq!(
trap([0, 1, 2, 0, 3, 0, 1, 2, 0, 0, 4, 2, 1, 2, 5, 0, 1, 2, 0, 2].to_vec()),
26
);
assert_eq!(trap([5, 5, 4, 7, 8, 2, 6, 9, 4, 5].to_vec()), 10);
assert_eq!(trap([2, 8, 5, 5, 6, 1, 7, 4, 5].to_vec()), 12);
assert_eq!(
trap(
[6, 4, 2, 0, 3, 2, 0, 3, 1, 4, 5, 3, 2, 7, 5, 3, 0, 1, 2, 1, 3, 4, 6, 8, 1, 3]
.to_vec()
),
83
);
assert_eq!(trap([9, 8, 3, 2, 3, 3, 4, 5, 7, 3].to_vec()), 22);
assert_eq!(
trap([1, 9, 7, 1, 3, 6, 4, 7, 4, 8, 3, 6, 3, 5, 3, 7].to_vec()),
39
);
}
}总结#
这道题印证了我们前面总结的规律：如果当前计算需要未来元素参与，不妨考虑下预处理, O(2n)那也是O(n)!（理直气壮）
不过这道题的难点其实在于得出：
-
可以根据列计算
-
当前列最大存水量是根据左右两边最高的俩列。