当前位置: 首页 > article >正文

《灵珠觉醒:从零到算法金仙的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函数查找区间内的最大值。
    • 常用操作:
      • leftMaxrightMax:记录左右区间的最大高度。

高阶优化:双指针与动态规划的智慧

哪吒元神中突然浮现金色铭文——「五火七禽扇灭火,双指针与动态规划显真身」。他意识到,可以通过双指针与动态规划优化接雨水的计算过程。

哪吒决定使用双指针法,维护两个指针分别从数组的两端向中心移动,同时记录左右两侧的最大高度。通过这种方式,他成功地计算了接住的雨水量,而且灵力消耗大幅减少。

int trap(vector<int>& height) {
   
    int n = height.size

http://www.kler.cn/a/590389.html

相关文章:

  • Kubernetes Network Policy使用场景
  • 微软远程桌面即将下架?Splashtop:更稳、更快、更安全的 RDP 替代方案
  • Django 5实用指南(十四)项目部署与性能优化【完】
  • 调用华为云API实现口罩识别
  • 从以太网 II 到 VLAN 和 Jumbo Frame:数据帧格式解读
  • 前端面试:如何减少项目里面 if-else?
  • 基于Python实现的结合U - Net与Transformer的神经网络用于视网膜血管分割的示例代码
  • 10 道面向 Java 开发者的 Linux 面试题及答案
  • SpringMVC响应页面及不同类型的数据,
  • Redis--补充类型
  • The Rust Programming Language 学习 (六)
  • 多元时间序列预测的范式革命:从数据异质性到基准重构
  • Elasticsearch 向量检索详解
  • 用maven生成springboot多模块项目
  • 【优化】系统性能优化步骤
  • UDP协议栈之整体架构处理
  • AI学习第二天--大模型压缩(量化、剪枝、蒸馏、低秩分解)
  • 上线后出现Bug测试该如何处理
  • Grafana 备份配置文件、数据库数据 和 仪表盘定义
  • 日语学习-日语知识点小记-构建基础-JLPT-N4N5阶段(23):たら ても