问题描述
这是一个典型的靠拢型双指针问题.
#![allow(unused)]
fn main() {
pub fn max_area1(height: Vec<i32>) -> i32 {
let len = height.len();
assert!(len > 1);
let mut max_area = 0;
let mut left = 0;
let mut right = len - 1;
while left < right {
let area: i32;
if height[left] < height[right] {
area = (right - left) as i32 * height[left];
left += 1;
} else {
area = (right - left) as i32 * height[right];
right -= 1;
}
max_area = area.max(max_area);
}
max_area
}
}
上面提到的代码实现是经典的写法, 但这里, 还可以针对里面的实现细节做一些优化.
具体来说就是, 判断当前指针的下个元素的值如果大不于当前值, 那就可以跳过下个元素,
因为它的面积值一定比当前根据两个指针计算的面积值要小.
#![allow(unused)]
fn main() {
pub fn max_area2(height: Vec<i32>) -> i32 {
let len = height.len();
assert!(len > 1);
let mut max_area = 0;
let mut left = 0;
let mut right = len - 1;
while left < right {
if height[left] < height[right] {
let curr = height[left];
let area = (right - left) as i32 * curr;
max_area = area.max(max_area);
while (left < right) && (height[left] <= curr) {
left += 1;
}
} else {
let curr = height[right];
let area = (right - left) as i32 * curr;
max_area = area.max(max_area);
while (left < right) && (height[right] <= curr) {
right -= 1;
}
}
}
max_area
}
}