专业做公司宣传网站,网站建设报价清单内容,国家认可的教育培训机构,给网站怎么做tag标签力扣上的经典问题#xff1a;接雨水
在众多的编程题库中#xff0c;力扣#xff08;LeetCode#xff09;是一个非常受欢迎的平台#xff0c;拥有大量的算法和数据结构练习题。其中#xff0c;接雨水#xff08;Trapping Rain Water#xff09;问题因其巧妙的思路和广泛…力扣上的经典问题接雨水
在众多的编程题库中力扣LeetCode是一个非常受欢迎的平台拥有大量的算法和数据结构练习题。其中接雨水Trapping Rain Water问题因其巧妙的思路和广泛的应用场景成为了经典的面试题之一。在这篇博客中我将介绍这个问题的背景解决思路并给出用C语言实现的解决方案。
问题描述
接雨水问题的描述如下
给定一个表示高度的数组数组中的每个元素表示一个柱子的高度柱子之间的宽度为1。求出这个柱子图形在下雨之后能够接多少雨水。
举例来说给定高度数组
height [0,1,0,2,1,0,1,3,2,1,2,1]该数组表示的图形如下图所示 ## ### ## ###############通过图形可以看出能够接住的雨水总量为6。
解题思路
解决这个问题的方法有很多种常见的有以下几种
暴力法对于每一个柱子分别计算其左右两边的最大高度然后取其最小值减去柱子自身的高度累加所有柱子能够接住的水量。动态编程预先计算每一个柱子的左边最高高度和右边最高高度然后同样计算水量。双指针法使用双指针从两端向中间遍历计算能够接住的水量。
下面我们主要介绍双指针法这种方法时间复杂度为O(n)空间复杂度为O(1)比较高效。
C语言代码实现
#include stdio.hint 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;
}代码解析 初始化变量 left 和 right 分别指向数组的两端。left_max 和 right_max 分别记录左右两边的最大高度。water 用于累加接住的雨水总量。 双指针遍历 当左指针指向的高度小于右指针指向的高度时处理左指针指向的柱子 如果当前高度大于或等于 left_max更新 left_max。否则将 left_max 减去当前高度得到当前柱子能接住的雨水量累加到 water。 当右指针指向的高度小于等于左指针指向的高度时处理右指针指向的柱子 如果当前高度大于或等于 right_max更新 right_max。否则将 right_max 减去当前高度得到当前柱子能接住的雨水量累加到 water。 输出结果最终 water 中累加的值即为总共能接住的雨水量。
总结
接雨水问题是一个经典的动态规划问题通过不同的方法可以优化时间和空间复杂度。双指针法因其较低的时间复杂度和空间复杂度成为了面试中常见的解法之一。希望这篇博客能够帮助大家更好地理解接雨水问题并掌握其解决思路和方法。 希望这篇博客对你有帮助如果你有任何问题或需要进一步的解释请随时告诉我。
