题目描述
公元2919年，人类终于发现了一颗宜居星球——X星。 现想在X星一片连绵起伏的山脉间建一个天热蓄水库，如何选取水库边界，使蓄水量最大？
要求：
山脉用正整数数组s表示，每个元素代表山脉的高度。
选取山脉上两个点作为蓄水库的边界，则边界内的区域可以蓄水，蓄水量需排除山脉占用的空间
蓄水量的高度为两边界的最小值。
如果出现多个满足条件的边界，应选取距离最近的一组边界。
输出边界下标（从0开始）和最大蓄水量；如果无法蓄水，则返回0，此时不返回边界。 例如，当山脉为s=[3,1,2]时，则选取s[0]和s[2]作为水库边界，则蓄水量为1，此时输出：0 2:1 当山脉s=[3,2,1]时，不存在合理的边界，此时输出：0。
输入描述
一行正整数，用空格隔开，例如输入
1 2 3
表示s=[1,2,3]
输出描述
当存在合理的水库边界时，输出左边界、空格、右边界、英文冒号、蓄水量；例如
0 2:1
当不存在合理的书库边界时，输出0；例如
0
备注
1 ≤ length(s) ≤ 10000
0 ≤ s[i] ≤ 10000
示例1
输入
1 9 6 2 5 4 9 3 7
输出
1 6:19
说明
经过分析，选取s[1]和s[6]，水库蓄水量为19（3+7+4+5）
示例2
输入
1 8 6 2 5 4 8 3 7
输出
1 6:15
说明
经过分析，选取s[1]和s[8]时，水库蓄水量为15；同样选取s[1]和s[6]时，水库蓄水量也为15。由于后者下标距离小（为5），故应选取后者。
def prefix_sum(height):
n = len(height)
prefix = [0] * (n + 1)
for i in range(1, n + 1):
prefix[i] = prefix[i - 1] + height[i - 1]
return prefix
def compare_water(height, prefix, left, right):
if right - left <= 1:
return 0
mid_area = prefix[right] - prefix[left + 1]
all_area = min(height[left], height[right]) * (right - left - 1)
water = all_area - mid_area
return max(water, 0)
def find_data(height):
if len(height) < 3:
return "-1 -1:0"
prefix = prefix_sum(height)
max_water = 0
min_distance = float('inf')
res_left = -1
res_right = -1
left = 0
right = len(height) - 1
while left < right:
water = compare_water(height, prefix, left, right)
# 更新最大储水量
if water > max_water:
max_water = water
min_distance = right - left
res_left, res_right = left, right
elif water == max_water and water > 0:
# 储水量相同时选择距离更近的
if right - left < min_distance:
min_distance = right - left
res_left, res_right = left, right
# 移动指针
if height[left] < height[right]:
left += 1
else:
right -= 1
return f"{res_left} {res_right}:{max_water}" if max_water > 0 else "-1 -1:0"
def main():
import sys
for line in sys.stdin:
line = line.strip()
if not line:
continue
height = list(map(int, line.split()))
print(find_data(height))
if __name__ == '__main__':
main()
这个算法的核心思想是双指针法解决最大储水容器问题，但有一些特殊的设计考虑：
核心算法思想
1. 双指针遍历策略
使用两个指针
left和right分别从数组的两端开始每次比较两端的柱子高度，移动较矮的一侧（贪心策略）
原因是：较矮的柱子限制了储水量，移动它可能找到更高的柱子，从而增加储水潜力
2. 储水量计算逻辑
储水量 = 容器的总容量 - 中间柱子的体积
容器总容量：
min(height[left], height[right]) × (right - left - 1)以较矮的柱子为基准水位
宽度是左右柱子间的距离减1（因为左右柱子本身不储水）
中间柱子体积：使用前缀和快速计算
prefix[right] - prefix[left + 1]实际储水量：
总容量 - 中间体积
3. 特殊优化目标
这个算法不仅要找到最大储水量，还要考虑：
优先最大储水量
储水量相同时，选择距离最近的一对柱子
通过
min_distance变量跟踪距离定义为
right - left
4. 前缀和优化
预处理前缀和数组
prefix使计算中间柱子体积的时间复杂度从 O(n) 降到 O(1)
prefix[i]表示前 i 个柱子的高度总和
时间复杂度分析
O(n)：双指针从两端向中间移动，总共最多 n-1 次移动
O(1)：每次计算储水量只需要常数时间（借助前缀和）
空间复杂度 O(n)：存储前缀和数组
算法正确性保证
为什么移动较矮的柱子是正确的？
当前容器容量受限于较矮的柱子
移动较高的柱子不会增加容量上限，因为上限由较矮的柱子决定
移动较矮的柱子可能找到更高的替代，从而可能增加容量
与经典"接雨水"问题的区别
经典接雨水问题（LeetCode 42）：
计算所有柱子能接的总雨水量
每个位置的水位由左右两边最高柱子中的较矮者决定
这个算法的问题：
只选择两个柱子作为容器的边界
计算这两个柱子之间的储水量
寻找储水量最大的一对柱子
应用场景
这种算法适用于：
选择水库的两个坝址，使蓄水量最大
建筑设计中选择两个支撑点
任何需要选择两个边界来最大化中间区域容积的问题
这个算法的优雅之处在于：
简单直观：用双指针扫描一遍即可
高效：O(n)时间复杂度
灵活：可以在寻找最大储水量的同时考虑其他因素（如距离）