《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(60)五火七禽扇灭火 - 接雨水(双指针与动态规划)
《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(60)五火七禽扇灭火 - 接雨水(双指针与动态规划)
哪吒在数据修仙界中继续他的修炼之旅。这一次,他来到了一片神秘的五火七禽扇谷,谷中有一片由高低不平的山墙组成的区域,山墙之间形成一个个可以接雨水的凹槽。谷口有一块巨大的石碑,上面刻着一行文字:“欲灭此谷之火,需以五火七禽扇之力,接雨水,双指针与动态规划显真身。”
哪吒定睛一看,石碑上还有一行小字:“高度数组[0,1,0,2,1,0,1,3,2,1,2,1]
可接的雨水总量为6
。”哪吒心中一动,他知道这是一道关于接雨水的难题,需要通过双指针与动态规划的方法来计算可以接住的雨水总量。
暴力解法:五火七禽扇的初次尝试
哪吒心想:“要计算接住的雨水,我可以逐个位置检查。”他催动五火七禽扇之力,从数组的左端开始,逐个位置计算该位置可以接住的雨水量。
int trap(vector<int>& height) {
int n = height.size();
int res = 0;
for (int i = 1; i < n - 1; ++i) {
int leftMax = 0, rightMax = 0;
for (int j = i; j >= 0; --j) {
leftMax = max(leftMax, height[j]);
}
for (int j = i; j < n; ++j) {
rightMax = max(rightMax, height[j]);
}
int water = min(leftMax, rightMax) - height[i];
if (water > 0) {
res += water;
}
}
return res;
}
哪吒成功地计算了接住的雨水量,但五火七禽扇的光芒却黯淡了下来。他意识到,这种方法虽然可行,但效率低下,尤其是当数组很长时,灵力消耗巨大。
C++语法点
在C++中,接雨水问题涉及到数组的遍历和最大值的查找。以下是一些重要特性:
-
数组遍历:
- 使用
for
循环遍历数组。 - 常用操作:
height[i]
:访问数组中的元素。
- 使用
-
最大值查找:
- 使用
max
函数查找区间内的最大值。 - 常用操作:
leftMax
和rightMax
:记录左右区间的最大高度。
- 使用
高阶优化:双指针与动态规划的智慧
哪吒元神中突然浮现金色铭文——「五火七禽扇灭火,双指针与动态规划显真身」。他意识到,可以通过双指针与动态规划优化接雨水的计算过程。
哪吒决定使用双指针法,维护两个指针分别从数组的两端向中心移动,同时记录左右两侧的最大高度。通过这种方式,他成功地计算了接住的雨水量,而且灵力消耗大幅减少。
int trap(vector<int>& height) {
int n = height.size