求柱状图存水量的Python无库算法实现（支持全特例处理）

核心思路 #

每个柱子位置能留存的水量，由其左侧最高柱子高度和右侧最高柱子高度中的较小值决定，公式为：当前存水量 = min(左侧最大高度, 右侧最大高度) - 当前柱子高度。将所有位置的存水量累加，即为总留存水量。

这里采用双指针法实现，无需额外存储左右最大高度数组，空间复杂度为O(1)，时间复杂度为O(n)，效率最优。

纯Python代码实现 #

# 读取输入并转换为整数列表
heights = list(map(int, input().split()))

# 处理空输入或无法存水的情况（柱子数≤2）
if len(heights) <= 2:
    print(0)
else:
    left = 0
    right = len(heights) - 1
    left_max = heights[left]
    right_max = heights[right]
    total_water = 0

    while left < right:
        if left_max < right_max:
            left += 1
            # 更新左侧已遍历区域的最大高度
            left_max = max(left_max, heights[left])
            # 累加当前位置存水量（若当前柱子更高，差值为0，不影响总和）
            total_water += left_max - heights[left]
        else:
            right -= 1
            # 更新右侧已遍历区域的最大高度
            right_max = max(right_max, heights[right])
            total_water += right_max - heights[right]

    print(total_water)

代码逐行解释 #

• 输入处理：读取用户输入的空格分隔数字，转换为整数列表；若列表长度≤2，无法形成存水空间，直接输出0。
• 指针与初始值：left和right分别指向数组首尾，left_max记录左侧已遍历的最大高度，right_max记录右侧已遍历的最大高度，total_water用于累加总水量。
• 双指针循环：
  • 若left_max < right_max：当前左指针位置的存水量由左侧最大高度决定，移动左指针后更新左侧最大高度，计算当前位置存水量并累加。
  • 反之：当前右指针位置的存水量由右侧最大高度决定，移动右指针后更新右侧最大高度，计算当前位置存水量并累加。
• 循环终止：当left与right相遇时，所有位置已遍历完毕，输出总水量。

示例验证（输入：4 1 3 5 2 3 4） #

1. 初始状态：left=0(4), right=6(4), left_max=4, right_max=4, total_water=0
2. 因left_max == right_max，移动右指针到5(3)，right_max仍为4，累加4-3=1，总水量=1
3. 移动右指针到4(2)，累加4-2=2，总水量=3
4. 移动右指针到3(5)，right_max更新为5，此时left_max < right_max，移动左指针到1(1)，累加4-1=3，总水量=6
5. 移动左指针到2(3)，累加4-3=1，总水量=7
6. 左指针移动到3，与右指针相遇，循环结束，输出7，与示例一致。

覆盖的特殊情况 #

• 空输入/单柱子/两个柱子：直接输出0
• 严格递增/递减数组：无存水空间，输出0
• 中间高两侧低的U型数组：如2 0 2，输出2
• 多峰值数组：如3 1 2 4 1 3，正确计算总存水量为5

内容的提问来源于stack exchange，提问作者root