接雨水-题目-算法

评论
179 views

"接雨水"问题是一个经典的算法问题，通常也称为Trapping Rain Water。这个问题描述如下：给定n个非负整数表示一系列宽度为1的墙，计算这些墙围成的容器能够容纳多少水。

解决这个问题的常见算法是利用双指针或者栈来进行处理。以下是一种基于双指针的解法：

  1. 使用两个指针left和right分别指向数组的两端。
  2. 初始化变量leftMax和rightMax为0，用来表示左侧和右侧的最大高度。
  3. 当left <= right时，进行循环：
  4. 如果height[left] < height[right]，则判断当前height[left]是否小于等于leftMax，如果是，则可以计算当前位置的积水量并更新leftMax；如果不是，则更新leftMax。
  5. 反之，如果height[left] >= height[right]，对right进行类似的操作。
  6. 循环结束后，得到的积水量即为答案。

这是一种简单而高效的解法，时间复杂度为O(n)，空间复杂度为O(1)。希望以上解法能够帮助你理解如何解决"接雨水"这个经典问题。

以下是用Python实现的“接雨水”问题的算法代码：

def trap(height):
    if not height:
        return 0

    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    result = 0

    while left <= right:
        if height[left] <= height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                result += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                result += right_max - height[right]
            right -= 1

    return result

# 示例
height = [0,1,0,2,1,0,1,3,2,1,2,1]
print(trap(height))  # 输出6

你可以将上述代码复制粘贴到Python环境中执行，以解决“接雨水”问题。在示例中，给定的墙高度列表为[0,1,0,2,1,0,1,3,2,1,2,1]，计算后得到的积水量为6。