代码随想录算法训练营第60天|84.柱状图中最大的矩形

84. 柱状图中最大的矩形

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

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

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

解题思路:

本题单调栈的解法和接雨水的题目是遥相呼应的。

为什么这么说呢,接雨水是找每个柱子左右两边第一个大于该柱子高度的柱子,而本题是找每个柱子左右两边第一个小于该柱子的柱子。

那么因为本题是要找每个柱子左右两边第一个小于该柱子的柱子,所以从栈头(元素从栈头弹出)到栈底的顺序应该是从大到小的顺序!

我来举一个例子,如图:

在这里插入图片描述

只有栈里从大到小的顺序,才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子。

所以本题单调栈的顺序正好与接雨水反过来。

此时大家应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度

在 height数组上后,都加了一个元素0, 为什么这么做呢?

如果数组本身就是升序的,例如[2,4,6,8],那么入栈之后 都是单调递减,一直都没有走计算操作。

如果数组本身是降序的,栈里没有元素了,那么为了避免空栈取值,直接跳过了计算结果的逻辑。

class Solution {
public:int largestRectangleArea(vector<int>& heights) {stack<int> st;heights.insert(heights.begin(), 0);heights.push_back(0);st.push(0);int result = 0;for (int i = 1; i < heights.size(); i++){while(!st.empty()&&heights[i]<heights[st.top()]){int middle = heights[st.top()];st.pop();int count  = middle*(i-st.top()-1);result = max(result,count);}st.push(i);}return result;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

24 JavaScript学习:this

this在对象方法中 在 JavaScript 中&#xff0c;this 的值取决于函数被调用的方式。在对象方法中&#xff0c;this 引用的是调用该方法的对象。 让我们看一个简单的例子&#xff1a; const person {firstName: John,lastName: Doe,fullName: function() {return this.firstN…

【webrtc】MessageHandler 3: 基于线程的消息处理:以sctp测试为例

消息处理可以用于模拟发包处理G:\CDN\rtcCli\m98\src\net\dcsctp\socket\dcsctp_socket_network_test.cc 这个实现中,onMessage还是仅对了一种消息进行处理,就是接收则模式下,打印带宽。当然,可能程序有多个消息,分别在不同的onmessage中执行?SctpActor:以一个恒定的速率…

C语言贪吃蛇项目

今天给大家带来一款简单的贪吃蛇游戏&#xff0c;一起随我来看看吧 游戏效果&#xff1a; 实现基本的功能&#xff1a; • 贪吃蛇地图绘制 • 蛇吃⻝物的功能&#xff1a;&#xff08;上、下、左、右⽅向键控制蛇的动作&#xff09; • 蛇撞墙死亡 • 蛇撞⾃⾝死亡 • 计算得分…

Flink 实时数仓(一)【实时数仓离线数仓对比】

前言 昨天技术面的时候&#xff0c;面试官说人家公司现在用的都是最新的技术&#xff0c;比如 Doris 等一些最新的工具&#xff0c;确实这些课是学校永远不会开设的&#xff0c;好在他说去了会带着我做一做。可是 ...... 学院这边确实不允许放人&#xff0c;唉&#xff0c;可惜…

Kubernetes 弃用Docker后 Kubelet切换到Containerd

containerd 是一个高级容器运行时&#xff0c;又名 容器管理器。简单来说&#xff0c;它是一个守护进程&#xff0c;在单个主机上管理完整的容器生命周期&#xff1a;创建、启动、停止容器、拉取和存储镜像、配置挂载、网络等。 containerd 旨在轻松嵌入到更大的系统中。Docke…

python项目入门新手攻略

最近工作需要接手了代码量比较大的python开发的项目&#xff0c;平时写python不多&#xff0c;记录一下如何熟悉项目。 分析调用流程-pycallgraph 因为代码量比较大&#xff0c;所以希望通过工具生成代码调用流程&#xff0c;因此用到了pycallgraph。 pycallgraph&#xff0…

windows Jenkins运行python+selenium打开浏览器一直无响应,运行中,还没有打开浏览器

一开始解决办法是把打开服务把Jenkins给禁用了 但是没有用&#xff0c;然后找到安装目录 C:\Program Files\Jenkins 在这个路径下&#xff0c;在地址栏输入cmd打开命令窗口运行Jenkins启动命令 java -jar jenkins.war --httpPort8080 打开浏览器进入链接 http://localhost:…

【Unity学习笔记】第十四 Prefab 概念解惑

目录 1 prefab、prefab变体、prefab覆盖和prefab 嵌套2 connect 与unpack3 prefab到底是什么&#xff0c;它和gameobject又有什么区别&#xff1f;4 为什么要用prefab&#xff1f;5 代码动态加载prefab6 为什么我unity PrefabUtility.InstantiatePrefab() 得到的是null7 Prefab…

Redis基本命令

目录 一、包含String、Set数据类型的基本命令 1、添加一个键值对 2、获取key所关联的字符串值 3、同时设置多个key-value 4、获取多个key对应的值 运行结果 5、将给定的value追加到原值的末尾 追加后效果 6、删除单个key 7、同时删除多个key 8、查询包含某个字符的k…

ubuntu入门

基础命令 cd 切换命令 ls 查看当前目录下所有的文件 cp a.c b.c 拷贝a.c 到 b.c touch a.c 创建a.c文件 mkdir file 创建文件夹file rm file 删除文件 rmdir 删除test文件夹 rmdir test/ mv 移动文件 mv a.c b.c 把a.c 替换成b.c ifconfig 查看电脑网络信息 rm xx 删…

Mybatis进阶(动态SQL)

文章目录 1.动态SQL1.基本介绍1.为什么需要动态SQL2.基本说明3.动态SQL常用标签 2.环境搭建1.新建子模块2.删除不必要的两个文件夹3.创建基本结构4.父模块的pom.xml5.jdbc.properties6.mybatis-config.xml7.MyBatisUtils.java8.MonsterMapper.java9.MonsterMapper.xml10.测试Mo…

工业互联网通讯协议—欧姆龙(Fins tcp)

一、场景 近期公司要对欧姆龙CP系列设备的数据采集&#xff0c;于是就研究了下欧姆龙的Fins Tcp协议。 二、Fins Tcp 组成字节说明固定头446494E53 FINS对应的ASCII码的十六进制长度4后面剩余指令的长度命令4 握手固定为&#xff1a;00000000 读写固定为&#xff1a;0000000…

Unity 实现新手引导遮罩

Unity 复写OnPopulateMesh 实现新手引导遮罩、包含点击事件触发区域判断 https://download.csdn.net/download/shenliang34/89247117

【第3节】“茴香豆“:搭建你的 RAG 智能助理

目录 1 基础知识1.1.RAG技术的概述1.2 RAG的基本结构有哪些呢&#xff1f;1.3 RAG 工作原理&#xff1a;1.4 向量数据库(Vector-DB )&#xff1a;1.5 RAG常见优化方法1.6RAG技术vs微调技术 2、茴香豆介绍2.1应用场景2.2 场景难点2.3 茴香豆的构建&#xff1a; 3 论文快读4 实践…

15(第十四章,大数据和数据科学)

目录 概述 基本概念 数据仓库/传统商务智能与数据科学的比较 数据科学的过程 大数据 大数据来源 数据湖 机器学习 监督学习 无监督学习 强化学习 扩展 1、数据仓库&#xff08;Data Warehouse&#xff09; 2、数据湖(Data Lake) 3、大数据平台1.0 4、数据中台 …

外贸企业邮箱是什么?Zoho Mail——你的专业外贸邮局

外贸企业邮箱是什么&#xff1f;做外贸行业必须要有企业邮箱吗&#xff1f;这是一些外贸企业的困惑。外贸企业邮箱和我们平时使用的个人邮箱有着几方面的不同。一是安全稳定&#xff1b;二是功能丰富性&#xff1b;三是存储空间更大。Zoho Mail企业邮箱在这些方面都能满足外贸企…

OpenCV如何实现背投(58)

返回:OpenCV系列文章目录&#xff08;持续更新中......&#xff09; 上一篇&#xff1a;OpenCV直方图比较(57) 下一篇&#xff1a;OpenCV如何模板匹配(59) 目标 在本教程中&#xff0c;您将学习&#xff1a; 什么是背投以及它为什么有用如何使用 OpenCV 函数 cv::calcBackP…

Java 获取 Outlook 邮箱的日历事件

Java 获取 Outlook 邮箱的日历事件 1.需求描述2.实现方案3.运行结果 IDE&#xff1a;IntelliJ IDEA 2022.3.3 JDK&#xff1a;1.8.0_351 Outlook&#xff1a;Microsoft Office 2016 1.需求描述 比如现在需要获取 Outlook 邮箱中四月的全部的会议安排&#xff0c;如下图所示 …

简单谈谈URL过滤在网络安全中的作用

用户花在网络上的时间越来越多&#xff0c;浏览他们最喜欢的网站&#xff0c;点击电子邮件链接&#xff0c;或利用各种基于网络的 SaaS 应用程序供个人和企业使用。虽然这种不受约束的网络活动对提高企业生产力非常有用&#xff0c;但也会使组织面临一系列安全和业务风险&#…

STM32G030F6P6TR 芯片TSSOP20 MCU单片机微控制器芯片

STM32G030F6P6TR 在物联网&#xff08;IoT&#xff09;设备中的典型应用案例包括但不限于以下几个方面&#xff1a; 1. 环境监测系统&#xff1a; 使用传感器来监测温度、湿度、气压等环境因素&#xff0c;并通过无线通信模块将数据发送到中央服务器或云端平台进行分析和监控。…