计算塔间蓄水量问题解析

1. 问题概述

在本教程中，我们将探讨一个经典的编程问题：给定一组高度不同的塔，计算它们之间能够蓄积的最大水量。

水会积聚在相邻塔之间形成的凹槽中，蓄水量由左右两侧最高塔中较矮的一侧决定。我们的目标是根据任意输入的塔序列，计算出总共能蓄积多少单位的水。

例如，以下是一组塔的高度分布：

图中，总共蓄积了 14 单位水：

• 塔 1 和塔 3 之间蓄积了 2 单位
• 塔 3 和塔 8 之间蓄积了 11 单位
• 塔 8 和塔 10 之间蓄积了 1 单位

2. 初级解法（暴力法）

基本思路是：逐个计算每个塔上方能蓄积的水量。

注意：

• 第一个和最后一个塔上方无法蓄水。
• 每个中间塔的蓄水量由其左右两侧最高塔中较矮的那一侧决定。

2.1. 实现逻辑

我们通过两层嵌套循环来找出每个塔左侧和右侧的最高塔，然后计算差值作为该位置的蓄水量。

Java 示例代码如下：

int NaiveAlgorithm(int[] towers) {
    int water = 0;
    for (int i = 1; i < towers.length - 1; i++) {
        int maxLeft = 0, maxRight = 0;

        // 找左边最高的塔
        for (int l = 0; l < i; l++) {
            maxLeft = Math.max(maxLeft, towers[l]);
        }

        // 找右边最高的塔
        for (int r = i + 1; r < towers.length; r++) {
            maxRight = Math.max(maxRight, towers[r]);
        }

        int minLeftRight = Math.min(maxLeft, maxRight);

        if (minLeftRight > towers[i]) {
            water += (minLeftRight - towers[i]);
        }
    }
    return water;
}

2.2. 示例解析

以塔 2 为例：

• 左侧最高是塔 1（高度为 5）
• 右侧最高是塔 8（高度为 9）
• 最小值为 5，当前塔高为 3，因此可蓄水 2 单位

2.3. 时间复杂度分析

• 时间复杂度：O(n²)
• 空间复杂度：O(1)

由于每座塔都要扫描其左右两侧所有塔，导致效率较低，尤其当塔的数量很大时会明显拖慢程序性能。

---

3. 双向扫描优化解法

为了优化暴力法的性能瓶颈，我们可以采用预处理的方式，提前计算每个塔左侧和右侧的最大高度。

3.1. 实现逻辑

我们进行两次扫描：

1. 从左到右扫描：记录每个塔左侧最高的塔的高度。
2. 从右到左扫描：记录每个塔右侧最高的塔的高度，并同时计算该位置的蓄水量。

Java 示例代码如下：

int TwoPassAlgorithm(int[] towers) {
    int n = towers.length;
    int[] maxLeft = new int[n];
    int currentMax = 0;

    // 从左往右记录每个位置左侧最高塔
    for (int i = 0; i < n; i++) {
        currentMax = Math.max(currentMax, towers[i]);
        maxLeft[i] = currentMax;
    }

    currentMax = 0;
    int water = 0;

    // 从右往左记录右侧最高塔并计算蓄水量
    for (int i = n - 1; i >= 0; i--) {
        currentMax = Math.max(currentMax, towers[i]);

        int limit = Math.min(maxLeft[i], currentMax);
        if (limit > towers[i]) {
            water += (limit - towers[i]);
        }
    }

    return water;
}

3.2. 示例解析

以塔 10 为例：

• 左侧最高是 9，右侧最高是 2
• 最小值是 2，当前塔高是 2，无法蓄水

以塔 9 为例：

• 左侧最高是 9，右侧最高是 2
• 最小值是 2，当前塔高是 1，可蓄水 1 单位

3.3. 性能分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

✅ 优点：

• 时间效率显著提升，尤其适合大规模输入数据
• 逻辑清晰，便于调试

❌ 缺点：

• 使用了额外数组，空间开销增加
• 理解和维护成本略高于暴力法

---

4. 总结与权衡

我们讨论了两种解决蓄水问题的方法：

方法	时间复杂度	空间复杂度	适用场景
暴力法	O(n²)	O(1)	小规模输入，代码简单
双向扫描法	O(n)	O(n)	大规模输入，性能优先

在实际开发中，我们需要根据项目需求权衡时间和空间的取舍。

⚠️ 踩坑提示：

• 不要盲目追求时间效率，忽略空间成本
• 理解算法原理比背诵代码更重要，否则容易在维护中踩坑

✅ 最佳实践建议：

• 面对类似问题，优先考虑是否可以使用预处理或双指针优化
• 熟悉常见算法优化技巧，例如“空间换时间”、“一次遍历”等

---