Python实现LeetCode接雨水问题：按行与按列思路解析

在LeetCode中的“接雨水”问题是一个经典的动态规划和数组操作题目，主要考察如何有效地测量一个二维数组中，当降雨发生时，每个单元格能够接收到的雨水量。这个问题有两个不同的解决方法，一个是按行接雨水，另一个是按列接雨水。 1. **按行接雨水**： - 首先，计算数组`height`中的最大值，表示最多有几行可能的雨水。 - 使用双层循环遍历数组，外层循环控制行，内层循环控制每个单元格。 - 当遇到比当前行（`i`）低的块（`height[j] < i`），说明可以收集雨水，累加到`temp`变量中，并将`start`标志设为True，表示从当前位置开始存储雨水。 - 如果遇到和当前行一样高或更高的块（`height[j] >= i`），说明之前的雨水收集结束，将`temp`加入答案`ans`并清零`temp`，同时重置`start`为False，以便开始新的雨水收集。 - 时间复杂度是`O(m * n)`，其中`m`是最大高度，`n`是数组长度，因为每个单元格都需要检查一次。 - 空间复杂度是`O(1)`，仅使用常数级别的额外空间。 2. **按列接雨水**： - 对于每一列，找到左边（从当前位置向左）和右边（从当前位置向右）的最大高度`Maxl`和`Maxr`。 - 计算这两个最大高度中的较小值`min(Maxl, Maxr)`，这是该列可能存储雨水的上限。 - 当当前单元格的高度`height[i]`小于这个最小高度时，可以收集雨水，水量等于`min`减去当前高度。 - 每列结束后，将所有列的水量加起来得到总水量。 - 时间复杂度同样是`O(m * n)`，因为每列都要进行查找最大值的操作。 - 空间复杂度也是`O(1)`，但这里需要额外的空间存储`Maxl`、`Maxr`和`min`。 这两个方法都是通过巧妙地利用数组结构和动态规划的思想，避免了复杂的遍历过程，使得算法效率得以提升。通过练习这样的题目，可以提升对数组操作和动态规划的理解，并锻炼解决问题的能力。