算法日记 40 day 单调栈

最后两题了,直接上题目。

题目:接雨水

42. 接雨水 - 力扣(LeetCode)

给定 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 个单位的雨水(蓝色部分表示雨水)。
 题目分析:

        这一题呢,可以使用暴力解法,双指针解法,和单调栈解法。本质上都是对每一个下标求左边第一个大于他的和右边第一个大于它的。为什么呢?就像一个木桶一样,确定底部之后,能装多少水取决于最短的那块板。所以在确定边界之后,最小的板和底部的差值就是能装的水了。

        不过我们需要确定,装水的多少按行还是按列。

按照行来计算如图: 

42.接雨水2

按照列来计算如图: 

42.接雨水1

以下就以按列来计算。大概的思路就是这样

 

具体的暴力解法如下,显然超时了,不过可以使用双指针优化。

public class Solution {
    public int Trap(int[] height) {
        int res=0;
        for(int i=0;i<height.Length;i++){
            if(i==0||i==height.Length-1) continue;
            int rHeight = height[i]; // 记录右边柱子的最高高度
            int lHeight = height[i]; // 记录左边柱子的最高高度
            for (int r = i + 1; r < height.Length; r++) {
                if (height[r] > rHeight) rHeight = height[r];
            }
            for (int l = i - 1; l >= 0; l--) {
                if (height[l] > lHeight) lHeight = height[l];
            }

            int h =Math.Min(rHeight,lHeight)-height[i];
            if(h>0) res+=h;
        }
        return res;
    }
}

单调栈解法

public class Solution {
    public int Trap(int[] height) {
        int res=0;
        if(height.Length<=2) return 0;
        Stack<int> st=new Stack<int>();
        st.Push(0);
        for(int i=1;i<height.Length;i++){
            while(st.Count>0&&height[i]>height[st.Peek()]){
                int mid=st.Peek();
                st.Pop();
                if(st.Count>0){
                    int h=Math.Min(height[st.Peek()],height[i])-height[mid];
                    int w=i-st.Peek()-1;
                    res+=h*w;
                }
            }
            st.Push(i);
        }
        return res;
    }
}

题目:柱状图中最大的矩形

84. 柱状图中最大的矩形 - 力扣(LeetCode)

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

 题目分析:

        这一题和上一题很相似,需要注意的是,接雨水需要木板高于底部,那么求面积呢?显然需要找到低于当前位置的左右边界,在边界内部才能取到最大面积(注意,不包括边界)。暴力和双指针解法和上面的一样,这里就不赘述了。

        既然我们找的是左右两边小于该值的,那么单调栈里面就应该是从栈顶到栈底递减的。所以就会出现一种情况,假设nums={4,3,2,1},入栈之后顺序保持不变,那就走不到我们求面积的逻辑里面了,所以我们给数组的两边都加上一个0,让它一定会出现增减。看看具体的实现。

public class Solution {
    public int LargestRectangleArea(int[] heights) {
        int res=0;
        Stack<int> st=new Stack<int>();
        int [] newHeights = new int[heights.Length + 2];
        Array.Copy(heights,0,newHeights,1,newHeights.Length-2);

        st.Push(0);
        for(int i=1;i<newHeights.Length;i++){
            while(newHeights[i]<newHeights[st.Peek()]){
                int mid=st.Peek();
                st.Pop();
                int left=st.Peek();
                int right=i;
                int cur=((right-left)-1)*newHeights[mid];
                res=Math.Max(cur,res);
            }
            st.Push(i);
        }
        return res;
    }
}

对于更详细的解析与其他语言的代码块,可以去代码随想录上查看。

代码随想录 (programmercarl.com)

已刷题目:130

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

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

相关文章

yagmail邮件发送库:如何用Python实现自动化邮件营销?

&#x1f3a5; 作者简介&#xff1a; CSDN\阿里云\腾讯云\华为云开发社区优质创作者&#xff0c;专注分享大数据、Python、数据库、人工智能等领域的优质内容 &#x1f338;个人主页&#xff1a; 长风清留杨的博客 &#x1f343;形式准则&#xff1a; 无论成就大小&#xff0c;…

【RL Base】强化学习:信赖域策略优化(TRPO)算法

&#x1f4e2;本篇文章是博主强化学习&#xff08;RL&#xff09;领域学习时&#xff0c;用于个人学习、研究或者欣赏使用&#xff0c;并基于博主对相关等领域的一些理解而记录的学习摘录和笔记&#xff0c;若有不当和侵权之处&#xff0c;指出后将会立即改正&#xff0c;还望谅…

黑马2024AI+JavaWeb开发入门Day04-SpringBootWeb入门-HTTP协议-分层解耦-IOCDI飞书作业

视频地址&#xff1a;哔哩哔哩 讲义作业飞书地址&#xff1a;day04作业&#xff08;IOC&DI&#xff09; 作业很简单&#xff0c;主要是练习拆分为三层架构controller、service、dao&#xff0c;并基于IOC & DI进行解耦。 1、结构&#xff1a; 2、代码 网盘链接&…

(长期更新)《零基础入门 ArcGIS(ArcMap) 》实验三----学校选址与路径规划(超超超详细!!!)

目录 实验三 学校选址与道路规划 3.1 实验内容及目的 3.1.1 实验内容 3.1.2 实验目的 3.2 实验方案 3.3 操作流程 3.3.1 环境设置 3.3.2 地势分析 &#xff08;1&#xff09;提取坡度: (2)重分类: 3.3.3 学校点分析 (1)欧氏距离: (2)重分类: 3.3.4 娱乐场所点分析 (1)欧氏距离…

【Python网络爬虫笔记】8- (BeautifulSoup)抓取电影天堂2024年最新电影,并保存所有电影名称和链接

目录 一. BeautifulSoup的作用二. 核心方法介绍2.1 构造函数2.2 find()方法2.3 find_all()方法2.4 select()方法 三. 网络爬虫中使用BeautifulSoup四、案例爬取结果 一. BeautifulSoup的作用 解析HTML/XML文档&#xff1a;它可以将复杂的HTML或XML文本转换为易于操作的树形结构…

MATLAB期末复习笔记(中)

目录 三、MATLAB函数和程序结构 1.MATLAB文件 2.变量和数据类型 &#xff08;1&#xff09;变量 &#xff08;2&#xff09;变量类型 &#xff08;3&#xff09;字符串 3.函数文件 &#xff08;1&#xff09;函数文件规范 &#xff08;2&#xff09;子函数和私有函数 &…

算法刷题Day8:BM30 二叉搜索树与双向链表

题目 牛客网题目传送门 思路 对二叉搜索树进行中序遍历&#xff0c;结果就是按序数组。因此想办法把前面遍历过的节点给记下来&#xff0c;记作pre。当遍历到某个节点node的时候&#xff0c;令前驱指向pre&#xff0c;然后让pre的后驱指向node。 代码 class TreeNode:def…

深入解析 Dubbo 中的常见问题及优化方案: 数据量限制与配置错误20241203

&#x1f31f; 深入解析 Dubbo 中的常见问题及优化方案&#xff1a;数据量限制与配置错误 在分布式系统中&#xff0c;Dubbo 作为高性能的 RPC 框架广泛应用于企业服务化架构。然而&#xff0c;在实际使用过程中&#xff0c;开发者往往会遇到一些复杂问题&#xff0c;比如 数据…

debian ubuntu armbian部署asp.net core 项目 开机自启动

我本地的环境是 rk3399机器&#xff0c;安装armbian系统。 1.安装.net core 组件 sudo apt-get update && \sudo apt-get install -y dotnet-sdk-8.0或者安装运行库&#xff0c;但无法生成编译项目 sudo apt-get update && \sudo apt-get install -y aspnet…

【AI系统】Ascend C 编程范式

Ascend C 编程范式 AI 的发展日新月异&#xff0c;AI 系统相关软件的更新迭代也是应接不暇&#xff0c;作为一本讲授理论的作品&#xff0c;我们将尽可能地讨论编程范式背后的原理和思考&#xff0c;而少体现代码实现&#xff0c;以期让读者理解 Ascend C 为何这样设计&#x…

hadoop环境配置-创建hadoop用户+更新apt+安装SSH+配置Java环境

一、创建hadoop用户(在vm安装的ubantu上打开控制台) 1、sudo useradd -m hadoop -s /bin/bash &#xff08;创建hadoop用户&#xff09; 2、sudo passwd hadoop (设置密码) 3、sudo adduser hadoop sudo&#xff08;将新建的hadoop用户设置为管理员&#xff09; 执行如下图 将…

嵌入式系统应用-LVGL的应用-平衡球游戏 part1

平衡球游戏 part1 1 平衡球游戏的界面设计2 界面设计2.1 背景设计2.2 球的设计2.3 移动球的坐标2.4 用鼠标移动这个球2.5 增加边框规则2.6 效果图 3 为小球增加增加动画效果3.1 增加移动效果代码3.2 具体效果图片 平衡球游戏 part2 第二部分文章在这里 1 平衡球游戏的界面设计…

从被动响应到主动帮助,ProActive Agent开启人机交互新篇章

在人工智能领域&#xff0c;我们正见证着一场革命性的变革。传统的AI助手&#xff0c;如ChatGPT&#xff0c;需要明确的指令才能执行任务。但现在&#xff0c;清华大学联合面壁智能等团队提出了一种全新的主动式Agent交互范式——ProActive Agent&#xff0c;它能够主动观察环境…

2.mysql 中一条更新语句的执行流程是怎样的呢?

前面我们系统了解了一个查询语句的执行流程&#xff0c;并介绍了执行过程中涉及的处理模块。 相信你还记得&#xff0c;一条查询语句的执行过程一般是经过连接器、分析器、优化器、执行器等功能模块&#xff0c;最后到达存储引擎。 那么&#xff0c;一条更新语句的执行流程又…

NaviveUI框架的使用 ——安装与引入(图标安装与引入)

文章目录 概述安装直接引入引入图标样式库 概述 &#x1f349;Naive UI 是一个轻量、现代化且易于使用的 Vue 3 UI 组件库&#xff0c;它提供了一组简洁、易用且功能强大的组件&#xff0c;旨在为开发者提供更高效的开发体验&#xff0c;特别是对于构建现代化的 web 应用程序。…

web vue 滑动选择 n宫格选中 九宫格选中

页面动态布局经常性要交给客户来操作&#xff0c;他们按时他们的习惯在同一个屏幕内显示若干个子视图&#xff0c;尤其是在医学影像领域对于影像的同屏显示目视对比显的更为重要。 来看看如下的用户体验&#xff1a; 设计为最多支持5行6列页面展示后&#xff0c;右侧的布局则动…

ELK的Filebeat

目录 传送门前言一、概念1. 主要功能2. 架构3. 使用场景4. 模块5. 监控与管理 二、下载地址三、Linux下7.6.2版本安装filebeat.yml配置文件参考&#xff08;不要直接拷贝用&#xff09;多行匹配配置过滤配置最终配置&#xff08;一、多行匹配、直接读取日志文件、EFK方案&#…

C#调用c++创建的动态链接库dll文件

在C#中调用外部DLL文件是一种常见的编程实践&#xff0c;它具有以下几个重要意义&#xff1a;1.代码重用&#xff1b;2.模块化&#xff1b;3.性能优化&#xff1b;4.安全性&#xff1b;5.跨平台兼容性&#xff1b;6.方便更新和维护&#xff1b;7.利用特定技术或框架&#xff1b…

重建大师重建的模型坐标有偏差怎么解决?

第一遍自由网空三&#xff0c;跑完之后刺点&#xff0c;然后控制点平差增强参数解算&#xff0c;方法如下&#xff1a; &#xff08;1&#xff09;跑完自由网空三后&#xff0c;选择编辑控制点&#xff0c;出现刺点窗口后&#xff0c;导入控制点参数 &#xff08;2&#xff09…

Apache Airflow 快速入门教程

Apache Airflow已经成为Python生态系统中管道编排的事实上的库。与类似的解决方案相反&#xff0c;由于它的简单性和可扩展性&#xff0c;它已经获得了普及。在本文中&#xff0c;我将尝试概述它的主要概念&#xff0c;并让您清楚地了解何时以及如何使用它。 Airflow应用场景 …