leetcode_rust/problems/p000_0xx/p000_011.rs
1//! # Description
2//!
3//! You are given an integer array height of length n. There are n vertical
4//! lines drawn such that the two endpoints of the ith line are `(i, 0)` and
5//! `(i, height[i])`.
6//!
7//! Find two lines that together with the x-axis form a container, such that
8//! the container contains the most water.
9//!
10//! Return the maximum amount of water a container can store.
11//!
12//! Notice that you may not slant the container.
13//!
14//! Example 1:
15//!
16//! 
17//!
18//! ```plain
19//! Input: height = [1,8,6,2,5,4,8,3,7]
20//! Output: 49
21//! Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7].
22//! In this case, the max area of water (blue section) the container can contain is 49.
23//! ```
24//!
25//! Example 2:
26//!
27//! ```plain
28//! Input: height = [1,1]
29//! Output: 1
30//! ```
31//!
32//! Constraints:
33//!
34//! - `n == height.length`
35//! - `2 $\leqslant$ n $\leqslant$ $10^5$`
36//! - `0 $\leqslant$ height[i] $\leqslant$ $10^4$`
37//!
38//! Find out [this blog](https://dongs.xyz/post/algorithm-container-with-most-water/) about this problem (though it's in Chinese).
39//!
40//! Sources: <https://leetcode.com/problems/container-with-most-water/description/>
41
42////////////////////////////////////////////////////////////////////////////////
43
44/// Container With Most Water
45///
46/// # Arguments
47/// * `height` - array of wall heights
48pub fn max_area(height: Vec<i32>) -> i32 {
49 alg_1(height)
50}
51
52use core::cmp::max;
53
54/// Traverse and find the the region which contains most water
55///
56/// # Arguments
57/// * `height` - array of wall heights
58fn alg_1(height: Vec<i32>) -> i32 {
59 let mut sidx: usize = 0;
60 let mut eidx = height.len() - 1;
61 let mut area_max = 0;
62 let area = |x: usize, y: usize| -> i32 {
63 return if height[x] >= height[y] {
64 height[y]
65 } else {
66 height[x]
67 } * (if x >= y { x - y } else { y - x }) as i32;
68 };
69
70 loop {
71 if sidx == eidx {
72 break;
73 }
74 area_max = max(area(sidx, eidx), area_max);
75 let mut moved = false;
76 if height[sidx] <= height[eidx] {
77 while sidx < eidx {
78 if height[sidx + 1] <= height[sidx] {
79 sidx += 1;
80 moved = true;
81 } else {
82 break;
83 }
84 }
85 if !moved {
86 sidx += 1;
87 }
88 } else {
89 while sidx < eidx {
90 if height[eidx - 1] <= height[eidx] {
91 eidx -= 1;
92 moved = true;
93 } else {
94 break;
95 }
96 }
97 if !moved {
98 eidx -= 1;
99 }
100 }
101 }
102
103 area_max
104}