摘要

盛最多水的容器查找器实现了在给定高度数组中找出两条线使得它们与 x 轴构成的容器能容纳最多水的功能。本文详细解析了输入解析、双指针法、暴力法、可视化表示等核心功能的代码实现细节。

1. 算法背景

1.1 问题描述

给定一个整数数组，每个元素表示一条垂直线的高度。找出两条线，使得它们与 x 轴构成的容器能容纳最多的水。

示例：

• 高度数组：[1, 8, 6, 2, 5, 4, 8, 3, 7]
• 最大面积：49（由位置 1 和位置 8 构成，高度为 min(8, 7) = 7，宽度为 7，面积 = 7 × 7 = 49）

1.2 应用场景

• 资源分配
• 区间选择
• 优化问题
• 算法竞赛

2. 核心算法原理

2.1 双指针法

从数组两端开始，使用两个指针向中间移动。每次移动较短的一边，因为移动较长的一边不会增加面积。时间复杂度 O(n)，空间复杂度 O(1)。

2.2 面积计算

面积 = 宽度 × min(左高度, 右高度)

3. 代码实现详细解析

3.1 输入解析模块

var heights: List<Int>? = null

payload.lines()
    .map { it.trim() }
    .filter { it.isNotEmpty() }
    .forEach { line ->
        when {
            line.startsWith("height=", ignoreCase = true) -> {
                val valuesStr = line.substringAfter("=").trim()
                try {
                    heights = valuesStr.split(",")
                        .map { it.trim() }
                        .filter { it.isNotEmpty() }
                        .map { it.toInt() }
                } catch (e: Exception) {
                    heights = null
                }
            }
        }
    }

if (heights == null) {
    // 尝试直接解析为逗号分隔的数字
    try {
        heights = payload.split(",")
            .map { it.trim() }
            .filter { it.isNotEmpty() }
            .map { it.toInt() }
    } catch (e: Exception) {
        return "❌ 无法解析高度数组，请使用格式：height=1,8,6,2,5,4,8,3,7 或直接输入数字用逗号分隔"
    }
}

代码解析：

这段代码实现了灵活的输入解析机制，支持两种输入格式。首先声明一个可空列表变量 heights，用于存储解析后的高度数组。

然后使用函数式编程风格处理输入：payload.lines() 将输入按行分割，map { it.trim() } 去除每行的首尾空白字符，filter { it.isNotEmpty() } 过滤空行。

在 forEach 循环中，如果行以 height= 开头（忽略大小写），提取等号后面的部分作为高度值字符串。然后使用 split(",") 按逗号分割，map { it.trim() } 去除每个元素的空白字符，filter { it.isNotEmpty() } 过滤空元素，map { it.toInt() } 将每个字符串转换为整数。

使用 try-catch 块捕获可能的异常，如果解析失败，将 heights 设置为 null。这种异常处理确保了程序的健壮性。

如果解析后高度数组为 null，则尝试直接解析输入：将整个输入按逗号分割并转换为整数数组。这种备选方案允许用户直接输入数字用逗号分隔，而不需要指定参数名，提高了输入的灵活性。

3.2 双指针法实现

fun maxAreaTwoPointer(heights: List<Int>): ResultData {
    var left = 0
    var right = heights.size - 1
    var maxArea = 0
    var bestLeft = 0
    var bestRight = 0
    val steps = mutableListOf<String>()

    steps.add("初始化: left=0, right=${heights.size - 1}")

    while (left < right) {
        val width = right - left
        val minHeight = minOf(heights[left], heights[right])
        val currentArea = width * minHeight

        steps.add("位置 [$left, $right]: 高度=[${heights[left]}, ${heights[right]}], 宽度=$width, 面积=$currentArea")

        if (currentArea > maxArea) {
            maxArea = currentArea
            bestLeft = left
            bestRight = right
            steps.add("  → 更新最大面积: $maxArea (位置 [$bestLeft, $bestRight])")
        }

        // 移动较短的一边
        if (heights[left] < heights[right]) {
            steps.add("  → 移动左指针 (左高度 ${heights[left]} < 右高度 ${heights[right]})")
            left++
        } else {
            steps.add("  → 移动右指针 (右高度 ${heights[right]} <= 左高度 ${heights[left]})")
            right--
        }
    }

    return ResultData(maxArea, bestLeft, bestRight, steps)
}

代码解析：

这是双指针法的核心实现，通过从两端向中间移动指针来查找最大面积。函数首先初始化变量：left 是左指针（初始值为 0，指向数组开头），right 是右指针（初始值为 heights.size - 1，指向数组末尾），maxArea 是当前找到的最大面积（初始值为 0），bestLeft 和 bestRight 是最大面积对应的左右位置，steps 是用于记录处理步骤的列表。

然后使用 while 循环，条件是 left < right，即两个指针还没有相遇。在循环内部，首先计算当前容器的参数：

宽度 width = right - left：这是两条线之间的距离，即容器的宽度。最小高度 minHeight = minOf(heights[left], heights[right])：这是两条线中较短的那条的高度，因为水的高度由较短的线决定，超过这个高度的水会溢出。

当前面积 currentArea = width * minHeight：这是当前容器能容纳的水量，等于宽度乘以最小高度。

记录当前步骤，包括左右位置、高度、宽度和面积信息，便于后续展示详细过程。

然后检查当前面积是否大于记录的最大面积。如果大于，更新最大面积和对应的左右位置，记录更新的步骤。这确保了算法能够找到全局最大面积。

接下来是关键步骤：移动指针。这里使用贪心策略，总是移动较短的那一边。如果 heights[left] < heights[right]，说明左边的线较短，将左指针向右移动（left++）；否则，将右指针向左移动（right--）。

为什么移动较短的一边？因为面积由宽度和最小高度决定。如果我们移动较长的一边，宽度会减小，但最小高度不会增加（甚至可能减小），所以面积只会减小或不变。如果我们移动较短的一边，虽然宽度也会减小，但最小高度可能增加（如果遇到更高的线），所以面积有可能增加。这种贪心策略保证了我们不会遗漏最优解。

循环结束后，返回最大面积、最佳位置和处理步骤。这个算法的时间复杂度是 O(n)，因为每个元素最多被访问一次；空间复杂度是 O(1)，因为只使用了固定数量的变量（虽然有一个 steps 列表，但在实际应用中可以省略）。

3.3 暴力法实现

fun maxAreaBruteForce(heights: List<Int>): Pair<Int, List<Pair<Int, Int>>> {
    var maxArea = 0
    val results = mutableListOf<Pair<Int, Int>>()

    for (i in heights.indices) {
        for (j in i + 1 until heights.size) {
            val width = j - i
            val minHeight = minOf(heights[i], heights[j])
            val area = width * minHeight

            if (area > maxArea) {
                maxArea = area
                results.clear()
                results.add(Pair(i, j))
            } else if (area == maxArea) {
                results.add(Pair(i, j))
            }
        }
    }

    return Pair(maxArea, results.distinct())
}

代码解析：

这是暴力法的实现，通过检查所有可能的数对来找到最大面积。函数首先初始化变量：maxArea 是当前找到的最大面积（初始值为 0），results 是存储所有最大面积对应位置的列表。

然后使用双重循环遍历所有可能的数对。外层循环变量 i 遍历数组的所有起始位置，内层循环变量 j 遍历从 i + 1 开始的所有结束位置。这种设计确保了每个数对只被检查一次，并且 j 始终大于 i，符合容器的定义（左边界在右边界之前）。

在循环内部，对于每个数对，计算容器的参数：宽度 width = j - i，最小高度 minHeight = minOf(heights[i], heights[j])，面积 area = width * minHeight。

然后检查当前面积是否大于记录的最大面积。如果大于，更新最大面积并清空结果列表，添加当前位置对。如果等于，则将当前位置对添加到结果列表中（可能存在多个相同最大面积的位置对）。

循环结束后，返回最大面积和所有最大面积对应的位置对列表。使用 distinct() 去除重复的位置对，虽然在这种实现中不会产生重复，但这是一个良好的防御性编程实践。

这个算法的时间复杂度是 O(n²)，因为需要检查所有可能的数对；空间复杂度是 O(1)，除了存储结果列表。虽然时间复杂度较高，但这种方法简单直观，容易理解和验证，通常用于验证双指针法的正确性。

3.4 可视化表示功能

if (heightArray.size <= 12) {
    builder.appendLine("📊 可视化表示")
    val maxHeight = heightArray.maxOrNull() ?: 0
    
    // 从顶部到底部绘制
    for (level in maxHeight downTo 1) {
        builder.append("高度 $level: ")
        for (i in heightArray.indices) {
            if (heightArray[i] >= level) {
                if (i == bestLeft || i == bestRight) {
                    builder.append("█ ")  // 最佳边界
                } else {
                    builder.append("| ")
                }
            } else {
                builder.append("  ")
            }
        }
        builder.appendLine()
    }
    
    // 底部标注
    builder.append("位置:   ")
    for (i in heightArray.indices) {
        builder.append("$i ")
    }
    builder.appendLine()
    
    builder.append("高度:   ")
    heightArray.forEach { h ->
        builder.append("$h ")
    }
    builder.appendLine()
    
    // 标记最佳容器
    builder.append("容器:   ")
    for (i in heightArray.indices) {
        when {
            i == bestLeft -> builder.append("L ")
            i == bestRight -> builder.append("R ")
            i in (bestLeft + 1) until bestRight -> builder.append("~ ")
            else -> builder.append("  ")
        }
    }
    builder.appendLine()
}

代码解析：

这段代码实现了直观的可视化表示功能，帮助用户理解容器的工作原理和最佳位置。首先检查数组长度是否小于等于 12，只有在较短数组时才进行可视化，避免输出过多信息。

然后获取数组中的最大高度，用于确定绘制的层数。使用 downTo 关键字从最大高度向下遍历到 1，这样可以从上到下绘制容器，符合直观的视觉习惯。

在每一层中，遍历数组的每个位置。如果该位置的高度大于等于当前层数，说明在这个高度有线条存在，需要绘制。使用不同的字符表示不同的情况：如果该位置是最佳容器的左边界或右边界（i == bestLeft || i == bestRight），使用 "█ " 字符标记，突出显示最佳边界；否则使用 "| " 字符表示普通线条。如果该位置的高度小于当前层数，说明在这个高度没有线条，使用两个空格占位。

循环结束后，在底部添加标注信息。首先标注每个位置的位置编号，便于用户识别。然后标注每个位置的高度值，显示数组的实际数据。最后标记最佳容器：使用 "L " 标记左边界，使用 "R " 标记右边界，使用 "~ " 标记容器内部的区域（从 bestLeft + 1 到 bestRight - 1），其他位置使用两个空格占位。

这种可视化表示非常直观，用户可以清楚地看到每个位置的高度、最佳容器的位置以及容器覆盖的区域，有助于理解算法的结果和容器的工作原理。

4. 算法复杂度分析

4.1 时间复杂度

• 双指针法：O(n)，每个元素最多被访问一次
• 暴力法：O(n²)，需要检查所有可能的数对
• 总体时间复杂度：O(n)（使用双指针法）

4.2 空间复杂度

• 双指针法：O(1)，只使用固定数量的变量
• 暴力法：O(k)，k 为最大面积对应位置对的数量（通常很小）
• 总体空间复杂度：O(1)

5. 算法优化建议

5.1 双指针法优化

双指针法已经是时间最优的算法，时间复杂度为 O(n)，无法进一步优化。

5.2 贪心策略说明

移动较短的一边是贪心策略的核心，这个策略保证了不会遗漏最优解，因为移动较长的一边只会减小面积。

5.3 提前终止优化

虽然双指针法已经是最优的，但在某些情况下可以添加提前终止条件，例如当剩余宽度乘以最大可能高度已经小于当前最大面积时。

6. 应用场景扩展

1. 资源分配：在给定资源约束下最大化收益
2. 区间选择：选择最优的区间组合
3. 优化问题：各种需要寻找最优解的优化问题
4. 算法竞赛：LeetCode 等平台的经典问题
5. 三维容器：扩展为三维空间的容器问题

7. 总结

盛最多水的容器查找器实现了两种查找方法，核心要点：

1. 双指针法：时间复杂度 O(n)，从两端向中间移动，移动较短的一边
2. 贪心策略：移动较短的一边保证了不遗漏最优解
3. 面积计算：面积 = 宽度 × min(左高度, 右高度)
4. 可视化表示：提供直观的图形化展示，帮助理解算法结果

通过深入理解代码实现，可以更好地应用这个算法解决实际问题，如资源分配、区间选择、优化问题等场景。双指针法和贪心策略的思想也可以扩展到其他类似的优化问题中。

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net