☆【前后缀】【双指针】Leetcode 42. 接雨水

【前后缀】【双指针】Leetcode 42. 接雨水

    • 解法1 前后缀分解
    • 解法2 双指针

---------------🎈🎈42. 接雨水 题目链接🎈🎈-------------------

解法1 前后缀分解

在这里插入图片描述

维护一个前缀(左侧最高)后缀(右侧最高)数组
把每一个小区间看做一个桶,桶的容量取决于左右壁中最低的那一个Min(leftmax,rightmax)
左壁就是当前这块及其左侧高度的最大值:前缀 leftmax
右壁就是当前这块及其右侧高度的最大值:后缀 rightmax
最终能装的水 = 当前小桶的容量-当前小柱子高度

时间复杂度O(N)
空间复杂度O(N)

class Solution {
    public int trap(int[] height) {
        // 把每一个小区间看做一个桶,桶的容量取决于左右壁中最低的那一个Min(leftmax,rightmax)
        // 左壁就是当前这块及其左侧高度的最大值:前缀 leftmax
        // 右壁就是当前这块及其右侧高度的最大值:后缀 rightmax
        // 能装的水 = 桶容量-柱子高度

        int[] leftmax = new int[height.length]; // 左边的最大高度
        int[] rightmax = new int[height.length]; // 右边的最大高度
        int templeftmax = 0;
        for(int i = 0; i < height.length;i++){ // 前缀数组
            if(height[i] > templeftmax){
                templeftmax = height[i];
            }
            leftmax[i] = templeftmax;
        }

        int temprightmax = 0;
        for(int i = height.length-1; i >=0;i--){ // 后缀数组
            if(height[i] > temprightmax){
                temprightmax = height[i];
            }
            rightmax[i] = temprightmax;
        }

        int totalWater = 0;
        // 同时遍历前后缀数组,两者取取Min即为桶内可以容纳的高度。之后减去筒高度即为水的高度,累加即可
        for(int i = 0; i< height.length; i++){
            totalWater += Math.min(leftmax[i],rightmax[i])-height[i];
        }
        return totalWater;
    }
}   

解法2 双指针

在这里插入图片描述
多做做吧 不行就看看动图

双指针法👿
while(left<right)
每次更新前缀最大值和后缀最大值
⭐️当 前缀最大值 < 后缀最大值时:当前的桶容量肯定为前缀最大值
⭐️当 后缀最大值 < 前缀最大值时:当前的桶容量肯定为后缀最大值

之后就更新totalwater = 当前桶容量- 底部高度即可

时间复杂度O(N)
空间复杂度O(1)
⭐️⭐️

class Solution {
    public int trap(int[] height) {
        int totalWater = 0;
        // 初始化双指针 一个指头一个指尾
        int left = 0;
        int right = height.length-1;
        // 前缀最大值和后缀最大值
        int preMax =0;
        int backMax = 0;
        
        // 双指针left< right遍历
        while(left < right){
            // 更新前缀最大值和后缀最大值
            preMax = Math.max(preMax, height[left]);
            backMax = Math.max(backMax, height[right]);
            // 1.当:前缀最大值 小于 后缀最大值:说明桶容量一定为前缀最大值!!!
            if(preMax < backMax){
                totalWater += (preMax-height[left]);  // 计算totalwater = 桶容量-柱子高度
                left++;
            }
            // 2.当:后缀最大值 小于 前缀最大值:说明桶容量一定为后缀最大值!!!
            if(preMax >= backMax){
                totalWater += (backMax-height[right]);  // 计算totalwater = 桶容量-柱子高度
                right--;
            }
            // 3.前缀最大值和后缀最大值相等的时候,随便归入一类就行
        }
        return totalWater;

    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/483922.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于python+vue高校门诊管理系统flask-django-php-nodejs

课题主要采用python开发语言、django框架和MySQL数据库开发技术以及基于Eclipse的编辑器。系统主要包括用户、用户充值、医生、挂号信息、检查开药、药品信息、药品入库、取药出库等功能&#xff0c;从而实现智能化的管理方式&#xff0c;提高工作效率。 语言&#xff1a;Pytho…

全流程基于GIS、python机器学习技术的地质灾害风险评价与信息化建库教程

原文链接&#xff1a;全流程基于GIS、python机器学习技术的地质灾害风险评价与信息化建库https://mp.weixin.qq.com/s?__bizMzUzNTczMDMxMg&mid2247598798&idx6&sn29597597dc134060576998b3302467f8&chksmfa820329cdf58a3fa73c04ac20a28fab7c7ee8fb15d0f8ac50…

python处理Excel的方法之xlrd

python处理Excel常用到的模块是xlrd。使用xlrd可以非常方便的处理Excel文档&#xff0c;下面介绍一下基本用法 打开文件 import xlrd data xlrd.open_workbook("c:\\skills.xls") 获取一个工作表 table data.sheet_by_name(uskills) #也可以 table data.sheet_by_…

测试CAN功能是否使能成功

一. 简介 上一篇文章学习了在 kernel内核源码如何使能 Linux 内核自带的 FlexCAN 驱动。通过配置kernel来实现。文章如下&#xff1a; 本文验证&#xff0c;开发板加载新生成的 zImage内核镜像文件&#xff0c;确定 CAN驱动是否已经成功使能。 二. 测试CAN驱动是否使能成功…

Go --- 编程知识点及其注意事项

new与make 二者都是用于内存分配&#xff0c;当声明的变量是引用类型时&#xff0c;不能给该变量赋值&#xff0c;因为没有分配空间。 我们可以用new和make对其进行内存分配。 首先说说new new函数定义 func new(Type) *Type传入一个类型&#xff0c;返回一个指向分配好该…

Nacos部署(一)Linux部署Nacos2.3.x单机环境

&#x1f60a; 作者&#xff1a; 一恍过去 &#x1f496; 主页&#xff1a; https://blog.csdn.net/zhuocailing3390 &#x1f38a; 社区&#xff1a; Java技术栈交流 &#x1f389; 主题&#xff1a; Nacos部署&#xff08;一&#xff09;Linux部署Nacos2.3.x单机环境 ⏱️…

鸿蒙开发学习【地图位置服务组件】

简介 移动终端设备已经深入人们日常生活的方方面面&#xff0c;如查看所在城市的天气、新闻轶事、出行打车、旅行导航、运动记录。这些习以为常的活动&#xff0c;都离不开定位用户终端设备的位置。 当用户处于这些丰富的使用场景中时&#xff0c;系统的位置定位能力可以提供…

深度解析:Elasticsearch写入请求处理流程

版本 Elasticsearch 8.x 原文链接&#xff1a;https://mp.weixin.qq.com/s/hZ_ZOLFUoRuWyqp47hqCgQ 今天来看下 Elasticsearch 中的写入流程。 不想看过程可以直接跳转文章末尾查看总结部分。最后附上个人理解的一个图。 从我们发出写入请求&#xff0c;到 Elasticsearch 接收请…

应急响应实战笔记03权限维持篇(7)

第7篇&#xff1a;常见WebShell管理工具 攻击者在入侵网站时&#xff0c;通常要通过各种方式写入Webshell&#xff0c;从而获得服务器的控制权限&#xff0c;比如执行系统命令、读取配置文件、窃取用户数据&#xff0c;篡改网站页面等操作。 本文介绍十款常用的Webshell管理工…

图论基础|深度优先dfs、广度优先bfs

dfs 与 bfs 区别 提到深度优先搜索&#xff08;dfs&#xff09;&#xff0c;就不得不说和广度优先搜索&#xff08;bfs&#xff09;有什么区别 先来了解dfs的过程&#xff0c;很多录友可能对dfs&#xff08;深度优先搜索&#xff09;&#xff0c;bfs&#xff08;广度优先搜索…

K8S之DaemonSet控制器

DaemonSet控制器 概念、原理解读、应用场景概述工作原理典型的应用场景介绍DaemonSet 与 Deployment 的区别 解读资源清单文件实践案例 概念、原理解读、应用场景 概述 DaemonSet控制器能够确保K8S集群所有的节点都分别运行一个相同的pod副本&#xff1b; 当集群中增加node节…

【嵌入式】Docker镜像构建指南:引领应用部署的革新之路

&#x1f9d1; 作者简介&#xff1a;阿里巴巴嵌入式技术专家&#xff0c;深耕嵌入式人工智能领域&#xff0c;具备多年的嵌入式硬件产品研发管理经验。 &#x1f4d2; 博客介绍&#xff1a;分享嵌入式开发领域的相关知识、经验、思考和感悟。提供嵌入式方向的学习指导、简历面…

绘制韦恩图

主要源于跟着Cell学作图 | 12.韦恩图(Vennerable包)-CSDN博客&#xff0c;增加了相关数据转换的处理。 韦恩图与upset差异 upset图&#xff1a;多个集合交集可视_upset图r语言代码自定义交集顺序-CSDN博客 rm(list ls()) #构建模型数据 group1 <- rep(c("1",…

AcWing 796. 子矩阵的和

这个题的重点是仿照一维的数组&#xff0c;所以a[N][N]也是从1索引开始的。画个图举个例子就非常清晰了 之所以不好理解是因为没画格子&#xff0c;一个格子代表一个点&#xff0c;就很好理解了。 java代码&#xff1a; import java.io.*; public class Main{static int N 1…

Java为什么是值传递?

Java为什么是值传递&#xff1f; 在我们调用方法的时候&#xff0c;通常会传递参数&#xff0c;那我们到底传递的是对象本身&#xff0c;还是仅仅是对象的拷贝对象呢&#xff1f; 先搞懂两个概念&#xff0c;形参和实参 形参和实参 实参&#xff08;实际参数&#xff0c;Ar…

【热门话题】ECMAScript vs JavaScript:理解两者间的联系与区别

&#x1f308;个人主页: 鑫宝Code &#x1f525;热门专栏: 闲话杂谈&#xff5c; 炫酷HTML | JavaScript基础 ​&#x1f4ab;个人格言: "如无必要&#xff0c;勿增实体" 文章目录 ECMAScript vs JavaScript&#xff1a;理解两者间的联系与区别1. ECMAScript&am…

Java设计模式之单例模式(多种实现方式)

虽然写了很多年代码&#xff0c;但是说真的对设计模式不是很熟练&#xff0c;虽然平时也会用到一些&#xff0c;但是都没有深入研究过&#xff0c;所以趁现在有空练下手 这章主要讲单例模式&#xff0c;也是最简单的一种模式&#xff0c;但是因为spring中bean的广泛应用&#…

车载测试项目实践 USD诊断 CANoe工具使用

本周末2天的时间&#xff0c;可以线下带大家对车载项目&#xff1a; uds诊断进行实操训练和CANoe工具的灵活使用 本博主从事新能源汽车的研发部&#xff0c;主要是嵌入式方面的&#xff0c;对车载测试的底层逻辑非常熟悉。 需要项目或者CANoe工具实操的可以关注并私信我

解决长尾问题,BEV-CLIP:自动驾驶中复杂场景的多模态BEV检索方法

解决长尾问题&#xff0c;BEV-CLIP&#xff1a;自动驾驶中复杂场景的多模态BEV检索方法 理想汽车的工作&#xff0c;原文&#xff0c;BEV-CLIP: Multi-modal BEV Retrieval Methodology for Complex Scene in Autonomous Driving 链接&#xff1a;https://arxiv.org/pdf/2401.…

算法思想总结:位运算

创作不易&#xff0c;感谢三连支持&#xff01;&#xff01; 一、常见的位运算总结 标题 二、位1的个数 . - 力扣&#xff08;LeetCode&#xff09; 利用第七条特性&#xff1a;n&&#xff08;n-1&#xff09;干掉最后一个1&#xff0c;然后每次都用count去统计&#xff…