0042.接雨水

https://leetcode.cn/problems/trapping-rain-water/

方法一：双指针

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

func trap(height []int) int {
	ans, lmax, rmax := 0, height[0], height[len(height)-1]
	for i, j := 0, len(height)-1; i <= j; {
		if lmax < height[i] {
			lmax = height[i]
		}
		if rmax < height[j] {
			rmax = height[j]
		}
		if lmax > rmax {
			ans += rmax - height[j]
			j--
		} else {
			ans += lmax - height[i]
			i++
		}
	}
	return ans
}

impl Solution {
    pub fn trap(height: Vec<i32>) -> i32 {
        let (mut i, mut j) = (0, height.len() - 1);
        let (mut ans, mut lmax, mut rmax) = (0, height[0], height[j]);
        while i < j {
            lmax = std::cmp::max(lmax, height[i]);
            rmax = std::cmp::max(rmax, height[j]);
            if lmax > rmax {
                ans += rmax - height[j];
                j -= 1;
            } else {
                ans += lmax - height[i];
                i += 1;
            }
        }
        ans
    }
}