python解 67 的内心积水区域

这个是python的题解，C++的题解如果没有的话去群里面压力flying他会帮你们写的不过这个解题思考可以看看或许对你们有一点启发.

算法思路

本题是经典的接雨水问题升级版——不仅要算每个位置的水深，还要统计连通区域的数量。

分析

1. 计算每个位置的水深

利用木桶效应：每个柱子能接多高的水，取决于它左右两边最高柱子的较小值。

• 预处理 left_max[i]：表示 $h_0$ 到 $h_{i-1}$ 中的最大值。
• 预处理 right_max[i]：表示 $h_{i+1}$ 到 $h_{n-1}$ 中的最大值。
• 位置 $i$ 的水深：water = max(0, min(left_max[i], right_max[i]) - h[i])

2. 统计连续的积水区域

用一个变量 in_Water 表示当前是否正处于一个积水区域内部。
遍历所有位置：

• 若 water > 0 且 in_Water == False：发现新区域的起点，计数器加一，并将 in_Water 置为 True。
• 若 water == 0：离开区域，in_Water 置为 False。

这样就能准确地将连续的水深格子合并成一个区域。

复杂度

• 时间复杂度：$O(n)$，三次线性扫描。（左扫描、右扫描、统计）
• 空间复杂度：$O(n)$，需要两个长度为 $n$ 的辅助数组。

代码

def count_water_regions(n, h):
    """
    统计积水区域的数量
    
    参数:
    n: 高度序列长度
    h: 高度序列列表
    
    返回:
    积水区域的数量
    """
    # 预处理左侧最高值
    left_max = [0] * n
    for i in range(1, n):
        left_max[i] = max(left_max[i-1], h[i-1])
    
    # 预处理右侧最高值
    right_max = [0] * n
    for i in range(n-2, -1, -1):
        right_max[i] = max(right_max[i+1], h[i+1])
    
    # 统计连续的积水区域
    regions = 0
    in_water = False
    
    for i in range(n):
        # 计算当前位置的水深
        water = max(0, min(left_max[i], right_max[i]) - h[i])
        
        if water > 0 and not in_water:
            # 发现新的积水区域
            regions += 1
            in_water = True
        elif water == 0:
            # 离开积水区域
            in_water = False
    
    return regions


def main():
    # 读取输入
    n = int(input())
    h = list(map(int, input().split()))
    
    # 计算并输出结果
    result = count_water_regions(n, h)
    print(result)


if __name__ == "__main__":
    main()