盛最多水的容器

题目要求

给定一个长度为 n 的整数数组 height，该数组代表了 n 条垂直线段的高度，每条线段的两个端点分别是 (i, 0) 和 (i, height[i])。任务是从这些线段中找出两条线，这两条线与 x 轴一起形成的容器可以存储最大量的水。

需要返回的是这个容器能够存储的水的最大量。注意，构成容器的线段必须是垂直于 x 轴的，也就是说，容器的边不能倾斜。

解题思路

这个问题可以通过双指针法来解决。初始时，我们可以将两个指针分别放在数组的开始和结束位置，这代表了容器的两边。容器的容量由两个指针之间的距离（容器的宽度）和两个指针中较短线段的高度（容器的高度）的乘积来决定。

解题步骤如下：

初始化两个指针：left 指针在数组的开始位置，right 指针在数组的结束位置。
初始化最大容量 max_area 为 0。
当 left 指针小于 right 指针时，执行以下步骤：
- 计算当前 left 和 right 指针所指线段构成的容器的容量，计算方式为 min(height[left], height[right]) * (right - left)。
- 更新 max_area，如果当前计算的容量大于 max_area，则将其赋值给 max_area。
- 移动指针以尝试找到更大的容量。由于容器的容量受限于较短的线段，我们应该移动较短的那个线段对应的指针。如果 height[left] < height[right]，则移动 left 指针，否则移动 right 指针。
重复步骤 3，直到 left 指针不再小于 right 指针。
返回 max_area 作为结果。

这种方法的关键在于，我们总是尝试通过移动较短的线段来找到可能更高的线段，因为这是增加容器容量的唯一方式。容器的宽度随着指针的移动是单调递减的，所以我们需要通过提高高度来弥补宽度的减少，以此来找到可能的最大容量。

Golang 版本

package main

import "fmt"

func maxArea(height []int) int {
    left, right := 0, len(height)-1
    maxArea := 0

    for left < right {
        // Calculate the area with the current boundary
        width := right - left
        high := min(height[left], height[right])
        currentArea := width * high
        // Update maxArea if the current area is greater
        maxArea = max(maxArea, currentArea)

        // Move the shorter line to try and find a taller line
        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }

    return maxArea
}

// Helper function to find the minimum of two integers
func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

// Helper function to find the maximum of two integers
func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func main() {
    // Example usage:
    height := []int{1,8,6,2,5,4,8,3,7}
    fmt.Println("The maximum amount of water that can be contained is:", maxArea(height))
}

这段代码定义了一个 maxArea 函数，它接受一个整数切片 height 作为参数，并返回一个整数，表示按照题目要求能够容纳的最大水量。主函数 main 提供了一个示例用法。

C++版本

#include <iostream>
#include <vector>
#include <algorithm>

int maxArea(std::vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int maxArea = 0;

    while (left < right) {
        // Calculate the area with the current boundary
        int width = right - left;
        int high = std::min(height[left], height[right]);
        int currentArea = width * high;
        // Update maxArea if the current area is greater
        maxArea = std::max(maxArea, currentArea);

        // Move the shorter line to try and find a taller line
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }

    return maxArea;
}

int main() {
    // Example usage:
    std::vector<int> height = {1,8,6,2,5,4,8,3,7};
    std::cout << "The maximum amount of water that can be contained is: " << maxArea(height) << std::endl;
    return 0;
}

这段代码定义了一个 maxArea 函数，它接受一个整数向量 height 作为参数，并返回一个整数，表示按照题目要求能够容纳的最大水量。main 函数提供了一个示例用法。

Python 版本

def max_area(height):
    left, right = 0, len(height) - 1
    max_area = 0

    while left < right:
        # Calculate the area with the current boundary
        width = right - left
        high = min(height[left], height[right])
        current_area = width * high
        # Update max_area if the current area is greater
        max_area = max(max_area, current_area)

        # Move the shorter line to try and find a taller line
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_area

# Example usage:
if __name__ == "__main__":
    height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
    print("The maximum amount of water that can be contained is:", max_area(height))

这段代码定义了一个 max_area 函数，它接受一个整数列表 height 作为参数，并返回一个整数，表示按照题目要求能够容纳的最大水量。if __name__ == "__main__": 部分提供了一个示例用法。

Java 版本

public class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int maxArea = 0;

        while (left < right) {
            // Calculate the area with the current boundary
            int width = right - left;
            int high = Math.min(height[left], height[right]);
            int currentArea = width * high;
            // Update maxArea if the current area is greater
            maxArea = Math.max(maxArea, currentArea);

            // Move the shorter line to try and find a taller line
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        System.out.println("The maximum amount of water that can be contained is: " + solution.maxArea(height));
    }
}

这段代码定义了一个名为 Solution 的类，其中包含了 maxArea 方法，该方法接受一个整数数组 height 作为参数，并返回一个整数，表示按照题目要求能够容纳的最大水量。main 方法提供了一个示例用法。

Rust 版本

fn max_area(height: Vec<i32>) -> i32 {
    let (mut left, mut right) = (0, height.len() - 1);
    let mut max_area = 0;

    while left < right {
        let width = (right - left) as i32;
        let high = std::cmp::min(height[left], height[right]);
        let current_area = width * high;
        max_area = std::cmp::max(max_area, current_area);

        if height[left] < height[right] {
            left += 1;
        } else {
            right -= 1;
        }
    }

    max_area
}

fn main() {
    let height = vec![1, 8, 6, 2, 5, 4, 8, 3, 7];
    println!("The maximum amount of water that can be contained is: {}", max_area(height));
}

这段代码定义了一个 max_area 函数，它接受一个整数向量 height 作为参数，并返回一个整数，表示按照题目要求能够容纳的最大水量。main 函数提供了一个示例用法。

总结

上述问题是一个经典的数组操作问题，通常称为“盛最多水的容器”。解决这个问题的关键在于使用双指针法。以下是解决这个问题的步骤：

初始化两个指针，一个在数组的开始位置（left），另一个在数组的结束位置（right）。
初始化一个变量来跟踪最大面积（maxArea）。
当左指针小于右指针时，执行以下操作：
- 计算当前两个指针之间的宽度（right - left）。
- 找出两个指针指向的高度中较小的一个。
- 计算当前的面积（当前宽度 * 较小的高度）。
- 如果当前面积大于之前记录的最大面积，则更新最大面积。
- 移动较短的那个指针（如果左边的高度小于右边的高度，则移动左指针；否则，移动右指针）。
当左指针不再小于右指针时，结束循环。
返回记录的最大面积。

这个算法的时间复杂度是 O(n)，因为每个元素只被访问一次。空间复杂度是 O(1)，因为只使用了常数空间。

在不同的编程语言中，这个算法的实现细节可能略有不同，但核心逻辑是一致的。例如，在 Rust 中，数组的长度是通过 len() 方法获取的，而在 Python 中则是通过内置的 len() 函数。同样，最小值和最大值的函数在不同的语言中也有所不同（如 std::min、std::max、Math.min、Math.max 等）。

hot-100