42. Trapping Rain Water Hard

1/**
2 * [42] Trapping Rain Water
3 *
4 * Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
5 *  
6 * Example 1:
7 * <img src="https://assets.leetcode.com/uploads/2018/10/22/rainwatertrap.png" style="width: 412px; height: 161px;" />
8 * Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
9 * Output: 6
10 * Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
11 * 
12 * Example 2:
13 * 
14 * Input: height = [4,2,0,3,2,5]
15 * Output: 9
16 * 
17 *  
18 * Constraints:
19 * 
20 * n == height.length
21 * 1 <= n <= 2 * 10^4
22 * 0 <= height[i] <= 10^5
23 * 
24 */
25pub struct Solution {}
26
27// problem: https://leetcode.com/problems/trapping-rain-water/
28// discuss: https://leetcode.com/problems/trapping-rain-water/discuss/?currentPage=1&orderBy=most_votes&query=
29
30// submission codes start here
31use std::cmp;
32impl Solution {
33    pub fn trap(height: Vec<i32>) -> i32 {
34        let (
35            mut left,
36            mut right,
37            mut start,
38            mut end,
39            mut result
40        ) = (0, 0, 0, height.len() - 1, 0);
41        while start < end {
42            left = cmp::max(left, height[start]);
43            right = cmp::max(right, height[end]);
44            if right > left {
45                result += left - height[start];
46                start += 1;
47            } else {
48                result += right - height[end];
49                end -= 1;
50            }
51        }
52        result
53    }
54}
55
56// submission codes end
57
58#[cfg(test)]
59mod tests {
60    use super::*;
61
62    #[test]
63    fn test_42() {
64        assert_eq!(Solution::trap(vec![4,2,0,3,2,5]), 9);
65    }
66}
67