乐趣区

关于算法:双指针进阶接雨水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
    }
}

退出移动版