目录

题目

算法思路

问题分析

核心思路 - 双指针法

时间复杂度分析

完整代码

---

题目

11. 盛最多水的容器

中等

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

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

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

说明：你不能倾斜容器。

示例 1：

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

示例 2：

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

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

算法思路

问题分析

我们要在数组中找到两条垂直线，使得它们与x轴构成的容器能盛最多的水。容器的盛水量由两个因素决定：

• 宽度：两条垂直线之间的距离 (j - i)

• 高度：两条线中较矮的那条线的高度 min(height[i], height[j])

盛水量公式：面积 = min(height[i], height[j]) × (j - i)

核心思路 - 双指针法

为什么用双指针？

• 暴力解法需要检查所有 O(n²) 对组合，时间复杂度太高

• 双指针可以在 O(n) 时间内找到最优解

算法步骤：

1. 初始化两个指针：left = 0, right = n-1

2. 初始化最大面积 maxArea = 0

3. 当 left < right 时循环：

   • 计算当前面积：area = min(height[left], height[right]) × (right - left)

   • 更新最大面积：maxArea = max(maxArea, area)

   • 移动较矮的那一边的指针：

     • 如果 height[left] < height[right]，则 left++

     • 否则 right--

4. 返回 maxArea

时间复杂度分析

• 时间复杂度：O(n)，两个指针总共移动 n-1 次

• 空间复杂度：O(1)，只使用了常数级别的额外空间

完整代码

package main

import "fmt"

func maxArea(height []int) int {
    left, right := 0, len(height)-1
    maxArea := 0
    
    for left < right {
        // 计算当前面积
        width := right - left
        currentHeight := min(height[left], height[right])
        area := width * currentHeight
        
        // 更新最大面积
        if area > maxArea {
            maxArea = area
        }
        
        // 移动较矮的那一边的指针
        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }
    
    return maxArea
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func main() {
    // 测试用例
    testCases := [][]int{
        {1, 8, 6, 2, 5, 4, 8, 3, 7}, // 期望: 49
        {1, 1},                       // 期望: 1
        {4, 3, 2, 1, 4},             // 期望: 16
        {1, 2, 1},                   // 期望: 2
    }
    
    for i, height := range testCases {
        result := maxArea(height)
        fmt.Printf("测试用例 %d: height = %v, 最大面积 = %d\n", i+1, height, result)
    }
}