11. Container With Most Water Medium

1/**
2 * [11] Container With Most Water
3 *
4 * Given n non-negative integers a1, a2, ..., an , where each represents a point at
5 * coordinate (i, ai). n vertical lines are drawn such that the two endpoints of
6 * the line i is at (i, ai) and (i, 0). Find two lines, which, together with the
7 * x-axis forms a container, such that the container contains the most water.
8 * Notice that you may not slant the container.
9 *  
10 * Example 1:
11 * <img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/07/17/question_11.jpg" style="width: 600px; height: 287px;" />
12 * Input: height = [1,8,6,2,5,4,8,3,7]
13 * Output: 49
14 * Explanation: The above vertical lines are represented by array
15 * [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section)
16 * the container can contain is 49.
17 *
18 * Example 2:
19 *
20 * Input: height = [1,1]
21 * Output: 1
22 *
23 * Example 3:
24 *
25 * Input: height = [4,3,2,1,4]
26 * Output: 16
27 *
28 * Example 4:
29 *
30 * Input: height = [1,2,1]
31 * Output: 2
32 *
33 *  
34 * Constraints:
35 *
36 * n == height.length
37 * 2 <= n <= 10^5
38 * 0 <= height[i] <= 10^4
39 *
40 */
41pub struct Solution {}
42
43// problem: https://leetcode.com/problems/container-with-most-water/
44// discuss: https://leetcode.com/problems/container-with-most-water/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47use std::cmp;
48impl Solution {
49    pub fn max_area(height: Vec<i32>) -> i32 {
50        let mut max = 0;
51        let mut s = 0;
52        let mut e = height.len() - 1;
53
54        while s < e {
55            max = cmp::max(max, (e - s) as i32 * cmp::min(height[s], height[e]));
56            if height[s] > height[e] {
57                e -= 1;
58            } else {
59                s += 1;
60            }
61        }
62        max
63    }
64}
65
66// submission codes end
67
68#[cfg(test)]
69mod tests {
70    use super::*;
71
72    #[test]
73    fn test_11() {
74        assert_eq!(Solution::max_area(vec![4, 3, 2, 1, 4]), 16);
75        assert_eq!(Solution::max_area(vec![1, 2, 1]), 2);
76        assert_eq!(Solution::max_area(vec![1, 1]), 1);
77    }
78}
79