当前位置：首页 > news >正文

扬中网站建设优帮云自己的网站怎么维护

news 2025/9/18 1:09:03

扬中网站建设优帮云,自己的网站怎么维护,免费拍卖网站模板,建网站业务员力扣上的经典问题：接雨水在众多的编程题库中，力扣（LeetCode）是一个非常受欢迎的平台，拥有大量的算法和数据结构练习题。其中，接雨水（Trapping Rain Water）问题因其巧妙的思路和广泛…

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

在众多的编程题库中，力扣（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.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;
}

代码解析

初始化变量：
- left 和 right 分别指向数组的两端。
- left_max 和 right_max 分别记录左右两边的最大高度。
- water 用于累加接住的雨水总量。
双指针遍历：
- 当左指针指向的高度小于右指针指向的高度时，处理左指针指向的柱子：
  - 如果当前高度大于或等于 left_max，更新 left_max。
  - 否则，将 left_max 减去当前高度，得到当前柱子能接住的雨水量，累加到 water。
- 当右指针指向的高度小于等于左指针指向的高度时，处理右指针指向的柱子：
  - 如果当前高度大于或等于 right_max，更新 right_max。
  - 否则，将 right_max 减去当前高度，得到当前柱子能接住的雨水量，累加到 water。
输出结果：最终 water 中累加的值即为总共能接住的雨水量。