关于算法:双指针进阶接雨水Rust语言描述

1 题目

42. 接雨水

2 思路

之前讲过，只有一一找出每个点左右的最大值，即可失去能够接的雨水；保护左右两个指针，以及left_max, right_max，这篇文章是看到论坛里有个同学用Rust求解该题，后果花了144ms……

3 代码

impl Solution {
    pub fn trap(height: Vec<i32>) -> i32 {
        let len          = height.len();
        let mut left     = 0;
        let mut left_max = height[left];
        let mut right    = len - 1;
        let mut right_max= height[right];
        let mut res      = 0;
        while left < right {
            if  height[left] <= height[right]{
                if height[left] >=  left_max{
                    left_max = height[left];
                }else{
                    res += left_max - height[left];
                }
                left += 1;
            }else{
                if height[right] >=  right_max{
                    right_max = height[right];
                }else{
                    res += right_max - height[right];
                }
                right -= 1;
            }
        }
        return res
    }
}