42. 接雨水-2

每天一道Rust-LeetCode(2019-12-27)

坚持每天一道题,刷题学习Rust.

题目描述

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

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 感谢 Marcos 贡献此图。


https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/10/22/rainwatertrap.png
示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
在真实的面试中遇到过这道题?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/trapping-rain-water
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

递减栈 (可以相等)
不用像上一种方法那么复杂
每次只计算增加的雨水量
以[5,2,1,2,1,5]
为例:
[5,2,1]
这时候来了2,那么增加了雨水是1
[5,2,2]->[5,2,2,1]
这时候来了5,
弹出1,增加(min(5,2)-1)1
弹出2,增加(min(5,2)-2)
3
弹出2, 增加(min(5,5)-2)*4

解题过程

struct Solution {}
impl Solution {
    pub fn trap(height: Vec<i32>) -> i32 {
        let mut stack = Vec::new();
        let mut total = 0;
        for i in 0..height.len() {
            //要把0也放进去,把0放进去,简化了很多问题
            while stack.len() > 0 && height[*stack.last().unwrap()] < height[i] {
                let pop_top = stack.pop().unwrap();
                if stack.is_empty() {
                    break;
                }
                let top = *stack.last().unwrap();
                let distance = i - top - 1;
                let height = min(height[i], height[top]) - height[pop_top];
                total += height * distance as i32
            }
            //            println!("push {}={}", i, height[i]);
            stack.push(i);
        }
        total
    }
}
#[cfg(test)]
mod test {
    use super::*;
    use crate::share::*;
    #[test]
    fn test() {
        let t = Solution::trap(vec![0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]);
        assert_eq!(t, 6);
        let t = Solution::trap(vec![4, 2, 3]);
        assert_eq!(t, 1);
        let t = Solution::trap(vec![5, 2, 1, 2, 1, 5]);
        assert_eq!(t, 14);
    }
}

一点感悟

如果不过滤0,那么碰到这种请0 1 2,这种情况,2进来的时候,很自然能够算出左侧0能够承载的雨水量就是0

其他

欢迎关注我的github,本项目文章所有代码都可以找到.