LeetCode——–接雨水python

题目不重述了。 小菜一枚，思路还是比较欠缺，按照leetcode题解的精选，用python写了一下。加深理解吧。 按行接雨水： 思路：首先寻找数组的最大值，即最多一共有几行。然后分别求每一行的雨水量。 从第一行开始，第一种情况是遇到比第一行低的块，可以存到一方水；第二种情况是遇到和第一行一样高或者比第一行要高的块，重新开始计算雨水量。 直到最高行，雨水量计算完毕。思路比较清晰，可以看力扣官网题解精选有图。 python代码： class Solution: def trap(self, height: List[int]) -> int: heightest=max 在LeetCode的“接雨水”问题中，我们面临一个经典的二维数组处理挑战。该问题的目标是计算在一个由整数组成的数组（代表地形）中，能够接住多少单位的雨水。数组中的每个元素代表一块地面的高度，雨水会在高度较低的地方积累。 我们可以采用“按行接雨水”的方法。这个思路是先找到数组中的最大高度，然后逐行计算每行的雨水量。对于每一行，我们需要考虑两种情况：一是遇到比当前行更低的块，这时雨水会积在这个块上，因此雨水量增加；二是遇到和当前行一样高或更高的块，我们需要重新开始计算。Python代码中定义了一个名为`Solution`的类，包含一个`trap`方法，它接受一个整数列表`height`作为输入，返回接雨水的总量。在`trap`方法中，首先找到数组的最大高度`heightest`，然后用一个外层循环遍历每一行，用一个内层循环计算每行的雨水量。 `trap`方法的实现中，用`start`变量表示是否已经遇到过一个和当前行一样高或更高的块，`temp`变量用于累计当前行的雨水量。外层循环从第二行开始（因为第一行的雨水量已经包含在最高行的计算中），内层循环遍历该行的所有元素。当`start`为真且遇到比当前行低的块时，雨水量增加；当遇到和当前行一样高或更高的块时，`start`重置为False，`temp`清零，重新开始计算。最后返回总雨水量`ans`。 时间复杂度为O(m * n)，其中m是最大高度，n是数组长度，因为我们需要遍历整个数组。空间复杂度为O(1)，因为我们只使用了常数级别的额外空间。 另一种方法是“按列接雨水”。这里我们对数组的每一列分别计算雨水量。对于每一列，我们需要找到左侧和右侧的最高点`Maxl`和`Maxr`，然后取两者中较小的那个。如果当前列的高度低于这个最小高度，那么就可以存储雨水，雨水量等于最小高度与当前列高度之差。遍历所有列，将各列的雨水量累加起来。这种方法也用到了两个循环，一个外层循环遍历每一列，一个内层循环找到当前列两侧的最高点。 动态规划方法进一步优化了按列接雨水的解决方案。我们创建两个辅助数组`left_max`和`right_max`，分别存储每列左侧和右侧的最大高度。对于`left_max`，我们从左到右遍历数组，将当前位置的值与前一个位置的`left_max`值比较，取较大者。对于`right_max`，我们从右向左遍历，将当前位置的值与后一个位置的`right_max`值比较。这样，我们避免了重复遍历，提高了效率。我们再次遍历数组，用`left_max`和`right_max`计算雨水量并累加。 列表解析是Python中简洁地创建新列表的一种方式。在本例中，`left_max`和`right_max`数组的初始化是通过列表解析完成的，分别用长度为`height`的列表填充了0值。这相当于使用传统的for循环初始化列表，但更简洁。 “接雨水”问题展示了多种处理二维数组数据结构的策略，包括遍历、比较、累加以及动态规划。通过这些方法，我们可以有效地解决这个问题，并学习到如何优化算法以减少时间复杂度。