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//! ![Image](/images/question_11.jpg)
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}
leetcode_rust/problems/p000_0xx/p000_011.rs

leetcode_rust/problems/p000_0xx/
p000_011.rs
