问题描述

给定一个长度为 n 的整数数组 height。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明： 你不能倾斜容器。

示例 1:

text

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2:

text

输入：height = [1,1]
输出：1

完整解决方案

go

func maxArea(height []int) int {
    // 边界情况处理：如果数组长度小于2，无法形成容器
    if len(height) < 2 {
        return 0
    }

    // 初始化双指针
    left, right := 0, len(height)-1
    maxArea := 0
    
    // 双指针向中间移动
    for left < right {
        // 计算当前容器的面积
        width := right - left
        currentHeight := min(height[left], height[right])
        currentArea := width * currentHeight
        
        // 更新最大面积
        if currentArea > maxArea {
            maxArea = currentArea
        }
        
        // 移动高度较小的指针
        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }
    return maxArea
}

// 辅助函数：返回两个整数中的较小值
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

// 辅助函数：返回两个整数中的较大值
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

算法解析

核心思路

使用双指针技巧，从数组的两端向中间移动，每次移动高度较小的指针，因为容器的盛水量由较短的那条边决定。

算法步骤详解

1. 边界情况处理

go

if len(height) < 2 {
    return 0
}

• 如果数组长度小于2，无法形成容器，直接返回0

2. 初始化双指针

go

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

• left 指针从数组开头开始

• right 指针从数组末尾开始

• maxArea 记录最大面积

3. 双指针遍历

go

for left < right {
    width := right - left
    currentHeight := min(height[left], height[right])
    currentArea := width * currentHeight
    
    if currentArea > maxArea {
        maxArea = currentArea
    }
    
    if height[left] < height[right] {
        left++
    } else {
        right--
    }
}

关键逻辑：

• 面积计算：面积 = 宽度 × 最小高度

• 指针移动策略：移动高度较小的指针，因为这样有可能找到更高的边来补偿宽度的减少

复杂度分析

• 时间复杂度：O(n)

  • 双指针只需遍历数组一次

  • 每个元素最多被访问一次

• 空间复杂度：O(1)

  • 只使用了常数级别的额外空间