《灵珠觉醒：从零到算法金仙的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