Solved 0042

guangsheng.li01 · guangsheng.li01 · commit 1c14b215c4c6 · 2020-02-04T14:00:54.000+08:00
diff --git a/src/a0042_trapping_rain_water.rs b/src/a0042_trapping_rain_water.rs
@@ -0,0 +1,49 @@
+/*
+ * [0042] trapping-rain-water
+ */
+
+pub struct Solution {}
+
+// solution impl starts here
+
+use std::cmp::max;
+impl Solution {
+    pub fn trap(height: Vec<i32>) -> i32 {
+        if height.len() < 3 {
+            return 0;
+        }
+
+        let (mut left, mut right, mut depth, mut result) = (0, height.len() - 1, std::i32::MIN, 0);
+        while left < right {
+            let p;
+            if height[left] < height[right] {
+                p = left;
+                left += 1;
+            } else {
+                p = right;
+                right -= 1;
+            }
+            depth = max(depth, height[p]);
+            if depth > height[p] {
+                result += depth - height[p];
+            }
+        }
+        result
+    }
+}
+
+// solution impl ends here
+
+// solution tests starts here
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_case0() {
+        assert_eq!(Solution::trap(vec![0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]), 6);
+    }
+}
+
+// solution tests ends here
diff --git a/src/lib.rs b/src/lib.rs
@@ -11,6 +11,7 @@ mod a0009_palindrome_number;
 mod a0026_remove_duplicates_from_sorted_array;
 mod a0027_remove_element;
 mod a0035_search_insert_position;
+mod a0042_trapping_rain_water;
 mod a0053_maximum_subarray;
 mod a0066_plus_one;
 mod a0088_merge_sorted_array;
