青岛建站费用,做电影网站用什么空间,北京百度总部电话,网络维护服务合同前言
记录一下刷题历程 力扣第42题 接雨水 接雨水
原题目#xff1a;给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。
示例 1#xff1a;
输入#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。
示例 1
输入height [0,1,0,2,1,0,1,3,2,1,2,1] 输出6 解释上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水。 示例 2
输入height [4,2,0,3,2,5] 输出9
分析
我们首先可以想到的就是统计一列左边和右边所有柱子的最高高度根据下图我们可以知道左右最高高度较低的值与当前柱子的高度差就是这一列能存储的水的高度。这是第一种方法但是需要O(n)的空间复杂度有没有优化空间呢我们来看方法2. 第二种方法我们其实并不需要同时计算左右两边的最高高度假如说我们对于当前列已经知道了左侧的最高高度只要右侧出现比左侧高度还要高那么左侧的最高高度就一定是水体的顶部然后我们可以计算该列的水体高度我们从数组两端向中间遍历分别计算左指针和左侧最高高度右指针和右侧最高高度找到对应结果较低的那一列直接更新结果即可
代码如下
第一种方法
class Solution {
public:// 接收一个整数数组 height表示每个柱子的高度返回可以接住的雨水总量int trap(vectorint height) {// n 表示柱子的总数int n height.size();// res 用于存储最终结果也就是可以接住的雨水总量int res 0;// 创建两个数组分别存储每个位置的左边最高柱子和右边最高柱子vectorint leftMax(n); // leftMax[i] 表示位置 i 左边最高的柱子vectorint rightMax(n); // rightMax[i] 表示位置 i 右边最高的柱子// 初始化 leftMax 数组的第一个元素因为第 0 个位置没有左边的柱子所以 leftMax[0] 就是 height[0]leftMax[0] height[0];// 计算每个位置的左边最高柱子从左到右遍历for(int i 1; i n - 1; i) {// leftMax[i] 是当前位置 i 和位置 i-1 的最高柱子之间的较大值leftMax[i] max(leftMax[i - 1], height[i]);}// 初始化 rightMax 数组的最后一个元素因为最后一个位置没有右边的柱子所以 rightMax[n-1] 就是 height[n-1]rightMax[n - 1] height[n - 1];// 计算每个位置的右边最高柱子从右到左遍历for(int i n - 2; i 0; i--) {// rightMax[i] 是当前位置 i 和位置 i1 的最高柱子之间的较大值rightMax[i] max(rightMax[i 1], height[i]);}// 遍历每个柱子计算该柱子上方能够接住的雨水for(int i 1; i n - 1; i) {// 当前位置的雨水容量等于左边和右边最高柱子之间的较小值减去当前柱子的高度int capacity min(leftMax[i], rightMax[i]) - height[i];// 累加结果capacity 是该位置能接住的水res capacity;}// 返回最终的接水量return res;}
};第二种方法
class Solution {
public:int trap(vectorint height) {// 获取柱子的总数int n height.size();// 如果柱子数小于3无法接住雨水直接返回0if (n 3) return 0;// 结果变量用于存储接住的雨水总量int res 0;// 左指针初始化为数组的起始位置int left 0;// 右指针初始化为数组的结束位置int right n - 1;// 左边最大值初始化为0int leftMax 0;// 右边最大值初始化为0int rightMax 0;// 双指针遍历直到两个指针重合while (left right) {// 更新左边最大值leftMax max(leftMax, height[left]);// 更新右边最大值rightMax max(rightMax, height[right]);// 如果左边最大值小于右边最大值处理左边的情况if (leftMax rightMax) {// 当前位置的水量 左边最大值 - 当前柱子的高度res leftMax - height[left];// 左指针向右移动left;} // 如果右边最大值小于等于左边最大值处理右边的情况else {// 当前位置的水量 右边最大值 - 当前柱子的高度res rightMax - height[right];// 右指针向左移动right--;}}// 返回接住的雨水总量return res;}
};代码解释
第一种方法主要思路
1.对于每个柱子而言能接住的水量取决于左边最高的柱子和右边最高的柱子以及当前位置柱子的高度。柱子能接住的水量是左、右柱子中较矮的那个减去当前柱子的高度。
为了快速得到每个柱子左边和右边的最大值我们通过预处理分别计算 leftMax 和 rightMax 数组。然后对于每个柱子计算它上方可以接住的水量并累加到结果中。
2.首先我们用两个数组 leftMax 和 rightMax 分别记录每个柱子左边和右边的最高柱子。
leftMax[i] 表示位置 i 左边的最高柱子包括 i 本身。 rightMax[i] 表示位置 i 右边的最高柱子包括 i 本身。
3.遍历 height 数组计算每个位置的左边最高值和右边最高值。
对于每个位置的柱子我们计算其能接住的雨水量min(leftMax[i], rightMax[i]) - height[i]。 累加每个位置的水量得到最终结果。
复杂度分析
时间复杂度该算法需要遍历三次数组时间复杂度为 O(n)。 空间复杂度需要额外的两个数组存储左边和右边的最大值空间复杂度为 O(n)。 这就是该算法的基本思路和实现方式。
第二种方法主要思路
1.初始化
获取 height 数组的大小 n存储在变量 n 中。 如果柱子的数量小于3例如0、1或2个柱子无法形成凹槽来接雨水直接返回0。 初始化结果变量 res 为0用于存储计算得到的雨水总量。 初始化两个指针 left 和 right 分别指向数组的起始和结束位置。 初始化 leftMax 和 rightMax 为0用于记录当前左边和右边的最大高度。
2.双指针遍历
当 left 指针小于 right 指针时进行循环。 在每次循环中 更新 leftMax 为当前位置左指针所指柱子的高度与之前 leftMax 的最大值之间的较大值。 更新 rightMax 为当前位置右指针所指柱子的高度与之前 rightMax 的最大值之间的较大值。
如果 leftMax 小于 rightMax说明左边的最高柱子更矮处理左边的情况
计算当前位置可以接住的雨水量等于 leftMax 减去当前柱子的高度。 将该雨水量累加到结果变量 res 中。 将左指针向右移动一位。
否则说明右边的最高柱子更矮或相等处理右边的情况
计算当前位置可以接住的雨水量等于 rightMax 减去当前柱子的高度。 将该雨水量累加到结果变量 res 中。 将右指针向左移动一位。
3.返回结果
循环结束后返回最终计算得到的接水总量 res。
复杂度分析
时间复杂度该算法的时间复杂度为 O(n)因为每个柱子位置在循环中只会被访问一次。 空间复杂度该算法的空间复杂度为 O(1)仅使用了常量级的额外空间不需要额外的数组。 这个双指针方法在时间复杂度和空间复杂度上都具有较好的性能是处理这个问题的一种高效解法。
