Created
March 3, 2019 07:41
-
-
Save frol/cb311e5480debec51c895dfcc179f429 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //! https://leetcode.com/problems/container-with-most-water/ | |
| //! | |
| //! Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, | |
| //! ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). | |
| //! Find two lines, which together with x-axis forms a container, such that the container contains | |
| //! the most water. | |
| //! | |
| //! Note: You may not slant the container and n is at least 2. | |
| fn max_area_brute_force(height: Vec<i32>) -> i32 { | |
| let mut max_square = 0; | |
| for (i, h1) in height.iter().enumerate() { | |
| for (j, h2) in height.iter().skip(i).enumerate() { | |
| let tmp_square = (j as i32) * (*h1.min(h2)); | |
| if tmp_square > max_square { | |
| max_square = tmp_square; | |
| } | |
| } | |
| } | |
| max_square | |
| } | |
| fn max_area_brute_force_fold(height: Vec<i32>) -> i32 { | |
| height.iter().enumerate().fold( | |
| 0, | |
| |max, (i, h1)| { | |
| height.iter().skip(i).enumerate().fold( | |
| max, | |
| |max, (j, h2)| max.max((j as i32) * (*h1.min(h2))) | |
| ) | |
| } | |
| ) | |
| } | |
| fn max_area_optimal(height: Vec<i32>) -> i32 { | |
| if height.is_empty() { | |
| return 0; | |
| } | |
| let mut h_left = height.iter().cloned(); | |
| let mut h_left_value = h_left.next().unwrap(); | |
| let mut h_right = height.iter().cloned().rev(); | |
| let mut h_right_value = h_right.next().unwrap(); | |
| let mut max_area = 0; | |
| for distance in (1..height.len() as i32).rev() { | |
| max_area = max_area.max(distance * h_left_value.min(h_right_value)); | |
| if h_left_value < h_right_value { | |
| h_left_value = h_left.next().unwrap(); | |
| } else { | |
| h_right_value = h_right.next().unwrap(); | |
| } | |
| } | |
| max_area | |
| } | |
| #[cfg(test)] | |
| mod tests { | |
| #[test] | |
| fn test_static_inputs() { | |
| let input = vec![1,8,6,2,5,4,8,3,7]; | |
| assert_eq!(super::max_area_brute_force(input.clone()), 49); | |
| assert_eq!(super::max_area_optimal(input), 49); | |
| } | |
| use quickcheck_macros::*; | |
| #[quickcheck] | |
| fn prop_correctness_against_brute_force(heights: Vec<i32>) -> bool { | |
| super::max_area_brute_force(heights.clone()) == super::max_area_optimal(heights) | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment