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

数学建模

1. 容器的定义：

• • 选择两条线，假设它们的索引分别为 i 和 j（i < j）。
  • 这两条线与 x 轴构成的容器是一个矩形，其宽度为 j - i，高度为两条线中较短的那条，即 min(height[i], height[j])。
  • 容器的面积为：area = (j - i) * min(height[i], height[j])。

1. 目标：

• • 最大化 area，即找到 max(area) 对所有可能的 (i, j) 对。

算法思路

1. 暴力法：

• • 遍历所有可能的 (i, j) 对，计算对应的面积，记录最大值。
  • 时间复杂度：O(n^2)，空间复杂度：O(1)。
  • 对于 n = 10^5，O(n^2) 会超时，因此需要更高效的算法。

1. 双指针法：

• • 初始化两个指针，left = 0 和 right = n - 1。
  • 计算当前面积 area = (right - left) * min(height[left], height[right])，并更新最大面积。
  • 移动指针：

• • • 如果 height[left] < height[right]，则 left++（因为移动 left 可能找到更高的线，从而可能增加面积）。
    • 否则，right--（因为移动 right 可能找到更高的线，从而可能增加面积）。

• • 重复上述过程直到 left >= right。
  • 时间复杂度：O(n)，空间复杂度：O(1)。

为什么双指针法有效？

• 关键观察：面积由两个因素决定：宽度和高度。宽度随着指针向内移动而减小，因此需要尽可能增加高度。
• 贪心策略：每次移动高度较小的指针，因为移动高度较大的指针不可能增加面积（宽度减小，高度受限于较小的那条线）。
• 正确性：双指针法不会错过最优解，因为：

• • 初始时，宽度最大。
  • 每次移动指针时，我们放弃了当前较小的那条线，但保留了较大的那条线，因此有可能在后续的迭代中找到更高的线来弥补宽度的损失。

代码实现

package demo

class Solution {
    public func maxArea(height: Array<Int64>): Int64 {
        // 初始化最大水量为0，用于记录遍历过程中找到的最大容量
        var maxWater: Int64 = 0
        
        // 初始化双指针：left指向数组起始位置，right指向数组末尾位置
        var left = 0
        var right = height.size - 1

        // 当左指针小于右指针时循环（保证能形成有效容器）
        while (left < right) {
            // 计算当前容器的高度：取左右指针所指高度的较小值（水会从短板溢出）
            let currentHeight = min(height[left], height[right])
            
            // 计算当前容器的宽度：右指针位置减去左指针位置
            let currentWidth = right - left
            
            // 计算当前容器的水量：高度 × 宽度
            let currentWater = currentHeight * currentWidth
            
            // 如果当前水量大于记录的最大水量，则更新最大水量
            if (currentWater > maxWater) {
                maxWater = currentWater
            }
            
            // 移动指针的策略：总是移动高度较小的一侧指针
            // 因为移动较高的一侧不会增加容量（容器高度由短板决定），而移动短板有可能遇到更高的板
            if (height[left] < height[right]) {
                left += 1  // 左指针右移：寻找可能更高的左边界
            } else {
                right -= 1  // 右指针左移：寻找可能更高的右边界
            }
        }
        
        // 返回遍历过程中找到的最大水量
        return maxWater
    }
}

main(): Unit {
    let solver = Solution()
    
    // 测试用例1：常规测试，验证算法正确性
    println(solver.maxArea([1,8,6,2,5,4,8,3,7]))  // 应输出49（由高度8和7，间距7构成）
    
    // 测试用例2：最小情况测试，验证边界处理
    println(solver.maxArea([1,1]))                // 应输出1（两根高度1的线间距1）
    
    // 测试用例3：对称情况测试，验证指针移动策略
    println(solver.maxArea([4,3,2,1,4]))         // 应输出16（首尾两个高度4，间距4）
    
    // 测试用例4：中间高两边低情况测试
    println(solver.maxArea([1,2,1]))              // 应输出2（中间高度2与任一边构成）
}

---