从双指针到单调栈，深挖“接雨水”的算法奥秘

从双指针到单调栈，深挖“接雨水”的算法奥秘

大家好，我是你们熟悉的算法领域大牛Echo_Wish。今天我们聊聊经典题目《接雨水》（Trapping Rain Water），不仅仅是讲解，而是深度对比两种高效解法：双指针和单调栈。这道题考察的不仅是算法能力，更是理解问题本质的功力。让我们一起从实现到优化，剖析这两种方法各自的亮点与适用场景。

题目背景

“接雨水”问题的核心是：给定一个数组，表示柱状图的高度，每个柱之间可以形成蓄水槽，问最多可以接多少雨水。这里要注意的是，蓄水量的关键取决于“短板效应”，也就是两侧较低的边界。

例如：对于数组[0,1,0,2,1,0,1,3,2,1,2,1]，柱状图如下：

       █
   █   █ █       █
 █ █ █ █ █ █ █   █
---------------------
0 1 0 2 1 0 1 3 2 1 2 1

最终可以接的雨水量为6。

方法一：双指针法

算法思路

双指针的核心思路是“木桶效应”。通过维护左右两个指针，动态更新左右两侧的最大高度，从而快速计算每个位置的蓄水量。

实现代码

下面是Python实现，内嵌注释方便理解：

def trap(height):
    if not height:  # 空数组处理
        return 0

    left, right = 0, len(height) - 1  # 左右指针初始化
    left_max, right_max = 0, 0  # 初始化两侧最大高度
    water = 0  # 蓄水量

    while left < right:
        if height[left] < height[right]:  # 决定当前区域由哪侧主导
            if height[left] >= left_max:
                left_max = height[left]  # 更新左侧最大高度
            else:
                water += left_max - height[left]  # 计算当前柱子蓄水量
            left += 1  # 左指针右移
        else:
            if height[right] >= right_max:
                right_max = height[right]  # 更新右侧最大高度
            else:
                water += right_max - height[right]  # 计算当前柱子蓄水量
            right -= 1  # 右指针左移

    return water

优点

1. 时间复杂度低：整个过程只需遍历数组一次，时间复杂度为O(n)。
2. 空间复杂度优：只需常数级的辅助变量，空间复杂度为O(1)。

局限性

双指针法对数组的边界情况处理较为敏感，比如左右端点高度相等的场景，可能需要格外注意边界更新逻辑。

方法二：单调栈法

算法思路

单调栈法则通过维护一个“单调递减栈”，来找到每个柱子的左、右边界。每当遇到比栈顶高度高的柱子，就可以开始计算雨水量。

实现代码

以下是Python实现，同样带有详细注释：

def trap(height):
    stack = []  # 初始化单调栈
    water = 0  # 蓄水量
    current = 0  # 当前遍历索引

    while current < len(height):
        # 如果当前高度大于栈顶柱子的高度，则可以开始计算蓄水量
        while stack and height[current] > height[stack[-1]]:
            top = stack.pop()  # 弹出栈顶元素
            if not stack:  # 如果栈为空，无法形成蓄水槽
                break

            distance = current - stack[-1] - 1  # 左右边界之间的宽度
            bounded_height = min(height[current], height[stack[-1]]) - height[top]  # 短板高度
            water += distance * bounded_height  # 计算蓄水量并累加

        stack.append(current)  # 当前柱子入栈
        current += 1  # 索引右移

    return water

优点

1. 适用场景广：对于复杂地形的柱状图，单调栈在逻辑处理上更具普适性。
2. 清晰直观：直接模拟边界变化过程，方便理解。

局限性

1. 空间消耗较高：由于需要维护栈，空间复杂度为O(n)。
2. 实现复杂度较高：栈操作需要额外的逻辑处理。

对比分析：如何选择？

实际应用

1. 如果你的输入数据较小或规则性较强（比如连续高度的柱状图），优先选择双指针法。
2. 如果面对的是高度变化复杂的柱状图，单调栈法可能更加直观且可靠。

写在最后

作为经典的算法题，“接雨水”不仅考验我们的代码能力，更需要在理解问题本质的基础上选取适合的解法。双指针法和单调栈法各有所长，关键在于熟练掌握思路并能灵活应用。