力扣上的经典问题：接雨水

力扣上的经典问题：接雨水

在众多的编程题库中，力扣（LeetCode）是一个非常受欢迎的平台，拥有大量的算法和数据结构练习题。其中，接雨水（Trapping Rain Water）问题因其巧妙的思路和广泛的应用场景，成为了经典的面试题之一。在这篇博客中，我将介绍这个问题的背景，解决思路，并给出用C语言实现的解决方案。

问题描述

接雨水问题的描述如下：

给定一个表示高度的数组，数组中的每个元素表示一个柱子的高度，柱子之间的宽度为1。求出这个柱子图形在下雨之后能够接多少雨水。

举例来说，给定高度数组：

height = [0,1,0,2,1,0,1,3,2,1,2,1]

该数组表示的图形如下图所示：

          ##   ###   ##  ###############

通过图形可以看出，能够接住的雨水总量为6。

解题思路

解决这个问题的方法有很多种，常见的有以下几种：

1. 暴力法：对于每一个柱子，分别计算其左右两边的最大高度，然后取其最小值减去柱子自身的高度，累加所有柱子能够接住的水量。
2. 动态编程：预先计算每一个柱子的左边最高高度和右边最高高度，然后同样计算水量。
3. 双指针法：使用双指针从两端向中间遍历，计算能够接住的水量。

下面我们主要介绍双指针法，这种方法时间复杂度为O(n)，空间复杂度为O(1)，比较高效。

C语言代码实现

#include <stdio.h>int trap(int* height, int heightSize) {if (heightSize == 0) return 0;int left = 0, right = heightSize - 1;int left_max = 0, right_max = 0;int water = 0;while (left < right) {if (height[left] < height[right]) {if (height[left] >= left_max) {left_max = height[left];} else {water += left_max - height[left];}left++;} else {if (height[right] >= right_max) {right_max = height[right];} else {water += right_max - height[right];}right--;}}return water;
}int main() {int height[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};int size = sizeof(height) / sizeof(height[0]);int result = trap(height, size);printf("The amount of trapped rain water is: %d\n", result);return 0;
}

代码解析

1. 初始化变量：

   • left 和 right 分别指向数组的两端。
   • left_max 和 right_max 分别记录左右两边的最大高度。
   • water 用于累加接住的雨水总量。

2. 双指针遍历：

   • 当左指针指向的高度小于右指针指向的高度时，处理左指针指向的柱子：
     • 如果当前高度大于或等于 left_max，更新 left_max。
     • 否则，将 left_max 减去当前高度，得到当前柱子能接住的雨水量，累加到 water。
   • 当右指针指向的高度小于等于左指针指向的高度时，处理右指针指向的柱子：
     • 如果当前高度大于或等于 right_max，更新 right_max。
     • 否则，将 right_max 减去当前高度，得到当前柱子能接住的雨水量，累加到 water。

3. 输出结果：最终 water 中累加的值即为总共能接住的雨水量。

总结

接雨水问题是一个经典的动态规划问题，通过不同的方法可以优化时间和空间复杂度。双指针法因其较低的时间复杂度和空间复杂度，成为了面试中常见的解法之一。希望这篇博客能够帮助大家更好地理解接雨水问题，并掌握其解决思路和方法。

---

希望这篇博客对你有帮助！如果你有任何问题或需要进一步的解释，请随时告诉我。