leetcode_rust/problems_cn/p000_0xx/
p000_011.rs

1//! # 题目描述
2//!
3//! 给定一个长度为 `n` 的整数数组 `height` 。有 `n` 条垂线，第 `i` 条线的两个端点是 `(i, 0)` 和 `(i, height[i])` 。
4//! 
5//! 找出其中的两条线，使得它们与 `x` 轴共同构成的容器可以容纳最多的水。
6//! 
7//! 返回容器可以储存的最大水量。
8//! 
9//! 说明：你不能倾斜容器。
10//! 
11//!  
12//! 
13//! 示例 1：
14//!
15//! ![Image](/images/question_11.jpg)
16//!
17//! ```plain
18//! 输入：[1,8,6,2,5,4,8,3,7]
19//! 输出：49 
20//! 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
21//! ```
22//!
23//! 示例 2：
24//! 
25//! ```plain
26//! 输入：height = [1,1]
27//! 输出：1
28//! ```
29//! 
30//! 提示：
31//!
32//! - `n == height.length`
33//! - `2 $\leqslant$ n $\leqslant$ $10^5$`
34//! - `0 $\leqslant$ height[i] $\leqslant$ $10^4$`
35//! 
36//! 您可以在 <https://dongs.xyz/post/algorithm-container-with-most-water/> 查看关于此问题的分析博文。
37//!
38//! Sources: <https://leetcode.cn/problems/container-with-most-water/>
39
40////////////////////////////////////////////////////////////////////////////////
41
42/// 盛最多水的容器
43///
44/// # 参数
45/// * `height` - 由器壁高度组成的数组
46pub fn max_area(height: Vec<i32>) -> i32 {
47    alg_1(height)
48}
49
50use core::cmp::max;
51
52/// 遍历整个数组，找到最大容水量的器壁组合
53/// 
54/// # 参数
55/// * `height` - 由器壁高度组成的数组
56fn alg_1(height: Vec<i32>) -> i32 {
57    let mut sidx: usize = 0;
58    let mut eidx = height.len() - 1;
59    let mut area_max = 0;
60    let area = |x: usize, y: usize| -> i32 {
61        return if height[x] >= height[y] {
62            height[y]
63        } else {
64            height[x]
65        } * (if x >= y { x - y } else { y - x }) as i32;
66    };
67
68    loop {
69        if sidx == eidx {
70            break;
71        }
72        area_max = max(area(sidx, eidx), area_max);
73        let mut moved = false;
74        if height[sidx] <= height[eidx] {
75            while sidx < eidx {
76                if height[sidx + 1] <= height[sidx] {
77                    sidx += 1;
78                    moved = true;
79                } else {
80                    break;
81                }
82            }
83            if !moved {
84                sidx += 1;
85            }
86        } else {
87            while sidx < eidx {
88                if height[eidx - 1] <= height[eidx] {
89                    eidx -= 1;
90                    moved = true;
91                } else {
92                    break;
93                }
94            }
95            if !moved {
96                eidx -= 1;
97            }
98        }
99    }
100
101    area_max
102}
leetcode_rust/problems_cn/p000_0xx/p000_011.rs

leetcode_rust/problems_cn/p000_0xx/
p000_011.rs
