1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

//! # Description
//!
//! You are given an integer array height of length n. There are n vertical
//! lines drawn such that the two endpoints of the ith line are `(i, 0)` and
//! `(i, height[i])`.
//!
//! Find two lines that together with the x-axis form a container, such that
//! the container contains the most water.
//!
//! Return the maximum amount of water a container can store.
//!
//! Notice that you may not slant the container.
//!
//! Example 1:
//!
//! ![Image](/images/question_11.jpg)
//!
//! ```plain
//! Input: height = [1,8,6,2,5,4,8,3,7]
//! Output: 49
//! Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7].
//! In this case, the max area of water (blue section) the container can contain is 49.
//! ```
//!
//! Example 2:
//!
//! ```plain
//! Input: height = [1,1]
//! Output: 1
//! ```
//!
//! Constraints:
//!
//! - `n == height.length`
//! - `2 $\leqslant$ n $\leqslant$ $10^5$`
//! - `0 $\leqslant$ height[i] $\leqslant$ $10^4$`
//! 
//! Find out [this blog](https://dongs.xyz/post/algorithm-container-with-most-water/) about this problem (though it's in Chinese).
//!
//! Sources: <https://leetcode.com/problems/container-with-most-water/description/>

////////////////////////////////////////////////////////////////////////////////

/// Container With Most Water
///
/// # Arguments
/// * `height` - array of wall heights
pub fn max_area(height: Vec<i32>) -> i32 {
    alg_1(height)
}

use core::cmp::max;

/// Traverse and find the the region which contains most water
/// 
/// # Arguments
/// * `height` - array of wall heights
fn alg_1(height: Vec<i32>) -> i32 {
    let mut sidx: usize = 0;
    let mut eidx = height.len() - 1;
    let mut area_max = 0;
    let area = |x: usize, y: usize| -> i32 {
        return if height[x] >= height[y] {
            height[y]
        } else {
            height[x]
        } * (if x >= y { x - y } else { y - x }) as i32;
    };

    loop {
        if sidx == eidx {
            break;
        }
        area_max = max(area(sidx, eidx), area_max);
        let mut moved = false;
        if height[sidx] <= height[eidx] {
            while sidx < eidx {
                if height[sidx + 1] <= height[sidx] {
                    sidx += 1;
                    moved = true;
                } else {
                    break;
                }
            }
            if !moved {
                sidx += 1;
            }
        } else {
            while sidx < eidx {
                if height[eidx - 1] <= height[eidx] {
                    eidx -= 1;
                    moved = true;
                } else {
                    break;
                }
            }
            if !moved {
                eidx -= 1;
            }
        }
    }

    area_max
}