0011. 盛最多水的容器 Container With Most Water

问题描述

这是一个典型的靠拢型双指针问题.

#![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
}
}