每日一题——柱状图中最大的矩形
柱状图中最大的矩形
题目链接
用什么数据结构?
要得到柱状图中最大的矩形,我们就必须要知道对于每一个高度heights[i]
,他所能勾勒出的矩形最大是多少(即宽度最大是多少)。
而对应到图上我们可以知道,要知道最大宽度,那就需要通过对下标的计算得到,因此要存储的也应该是每个高度对应的下标。
即:通过存储的下标索引找到对应的高度,同时快速计算出宽度,最终得到面积
我们就拿上面的例子进行分析:
- 一开始遍历的柱形高度是2,但以这一高度所确定的矩形还不能确定其面积的最大值,因此继续遍历
- 第二个柱形高度为1,此时这一高度所确定的最大矩形还不能确定。但是它前面的下标为0的柱形所确定的最大矩形就可以确定了。因为下标为1的这个柱形高度比下标为0的小,矮的卡在了高的后面,那么这个高的就不能向右扩展了。
- 这个时候,我们也就能计算下标为0的这一高度所能确定的最大矩形的面积了。同时,既然这一下标的高度已经确定,我们也就可以忽略这一下标代表的高度了,我们将其标灰。
-
第三个高度为5,由同样的分析可得,下标为2和下标为1的高度都不能确定其最大的矩形。继续遍历。
-
第四个高度为6,同样,高度为
1,5,6
的三个柱形也同样不能确定最大的矩形,继续便利。 -
第五个高度为2,小于下标为3的高度,因此下标为3高度为6的柱形确定的最大矩形就知道了。面积
size = 6 * (4-2-1) = 6
,同时由于这个柱形已经计算,就将其忽略、标灰。-
下标为4高度为2的柱形仍低于下标为2高度为5的柱形,因此下标为2高度为5的柱形确定的最大矩形也就知道了。面积
size = 5 * (4-1-1) = 10
,同时将这一柱形忽略、标灰。 -
下标为4高度为2的柱形高于下标为1高度为1的柱形,因此这两个柱形仍不能确定其最大的矩形,继续遍历。
-
-
第六个的高度为3,由同样的分析,高度为
1,2,3
的柱形都不能确定其最大的矩形
此时我们就遍历完了整个heights
数组,但是我们还有三个高度的最大矩形还没有确定,为了处理这三个数据,我们可以假设下标为6的柱形的高度为0(小于1都可以)
- 这样,下标为5高度为3的柱形就被夹在了两个较矮柱形的中间,其最大矩形也就确定了。
size = 3 * (6-4-1) = 3
- 同理,下标为4高度为2的矩形面积为:
size = 2 * (6-1-1) = 8
- 此时,只剩下下标为1高度为1的柱形,他是所有柱形中最低的柱形,所以它最大矩形的宽度就是整个数组的长度,因此面积
size = 1 * 6 = 6
至此,每个柱形所确定的最大矩形都已经分析完毕。
由上面的分析我们可以得出以下结论:
- 存储下标时,我们是从左到右存储的,但是计算下标对应的高度所确定的矩形面积时,是从右向左计算的(例如是先计算高度为6的面积在计算高度为5的面积),这符合先入后出的特性,因此这一题我们要用到的数据结构是栈。
- 之所以能确定一个柱形的最大矩形,就是在他右边碰到了比他更低的柱形(因为这个更低的柱形限制了这个高柱形的扩张)。因此这个栈存放的下标对应的高度应该是单调非递减的(注意不是单调递增),只要碰到递减的情况,就说明可以计算栈顶元素所代表高度的矩形面积了。
- 这个栈之所以要单调非递减时要考虑到进栈元素等于栈顶元素的情况。如下图:
- 如果将栈设计为单调递增的,那么当进栈元素5入栈时,栈顶元素5就要出栈,并计算其面积,但问题是这个进栈元素5并不小于这个栈顶元素5,那么这个栈顶元素5所确定的最大矩形也就不能确定。
- 因此进栈元素等于栈顶元素时,栈顶元素不要出栈。即这个栈为单调非递减的。
考虑特殊情况(添加哨兵位)
- 情况一:计算宽度时栈空。如下图:
此时,栈中存储的下标为[0]
,进栈下标对应的高度小于栈顶元素对应的高度,栈顶元素需要出栈,并计算其高度对应的最大矩形。现在问题来了,栈顶元素出栈后栈为空,没有下标用来计算宽度,这里就要用if(stackEmpty)
来进行特殊处理,但显然这是不方便的。因此我们可以在heights
数组的最前面加入一个高度0
,这样我们就可以保证栈中始终留有数据(这个0不可能出栈),也就可以更加方便的计算宽度了。
- 情况二:遍历完
heights
数组后,栈中还留有有效数据(部分柱形的最大矩形还未确定),如下图:
要计算出每个柱形的最大矩形,也就是要将栈中的每个下标都出栈,而要确保每个下标都可以出栈,那就要保证进栈下标代表的高度要小于栈中元素对应的高度,因此我们可以在heights
数组的末尾再加上一个0
,这样就可以保证在遍历完heights
数组的同时,每个高度的最大矩形都可以被计算了。
这两个高度为0,站在数组两边的柱形,就是我们常说的哨兵
实现代码
int largestRectangleArea(int* heights, int heightsSize){//添加哨兵位:heights = (int*)realloc(heights, sizeof(int) * (heightsSize + 2));heights[heightsSize + 1] = 0; //尾部添加0for (int i = heightsSize; i > 0; i--)heights[i] = heights[i - 1];heights[0] = 0; //头部添加0int *stack = (int*)malloc(sizeof(int) * (heightsSize + 2));int top = 0;int ret_size = 0;for (int i = 0; i < heightsSize + 2; i++){//当栈不为空并且进栈元素小于栈顶元素//就开始计算矩形面积while (top != 0 && heights[i] < heights[stack[top - 1]]){//栈顶元素出栈int high_index = stack[top - 1];top--;int wide = i - stack[top - 1] - 1; //宽度int high = heights[high_index]; //高度ret_size = ret_size > wide * high ? ret_size : wide * high;}//计算完成后或者没有进入循环,进栈元素都要入栈stack[top++] = i;}free(stack); //释放栈return ret_size;
}
相关文章:

每日一题——柱状图中最大的矩形
柱状图中最大的矩形 题目链接 用什么数据结构? 要得到柱状图中最大的矩形,我们就必须要知道对于每一个高度heights[i],他所能勾勒出的矩形最大是多少(即宽度最大是多少)。 而对应到图上我们可以知道,要知…...

Banana Pi推出基于龙芯2K1000LA处理器的信创工业控制开发平台
Banana Pi推出基于龙芯2K1000LA处理器的信创工业控制开发平台:BPI-5202信创工业控制开发平台 BPI-5202 龙芯2K1000LA 信创工业控制开发平台 1.1 工控机的应用场景 物联网的狂潮,既是一场众多的计算机软硬件厂家(也包括通讯方案和产品厂家&…...

springCloud整合Zookeeper的时候调用找不到服务
SpringCloud整合Zookeeper的时候调用找不到服务 首先,我们在注册中心注册了这个服务: 然后我们使用RestTemplate 调用的时候发现失败了:找不到这个服务: 找了很多资料发现这个必须要加上负载才行 BeanLoadBalanced //负载publi…...

【kubernetes】使用kubepshere部署中间件服务
KubeSphere部署中间件服务 入门使用KubeSphere部署单机版MySQL、Redis、RabbitMQ 记录一下搭建过程 (内容学习于尚硅谷云原生课程) 环境准备 VMware虚拟机k8s集群,一主两从,master也作为工作节点;KubeSphere k8skubesphere devops比较占用磁…...

如何从tabbar页面传数据
无论是百度小程序还是微信小程序,app.json中规定的tabbar页面是不支持传参的,例如: <navigator url../service/service?typeid6 openType"switchTab"> 服务项目 </navigator> 上面的navigater跳转有个属性&#…...

软考高级系统架构设计师系列论文七十四:基于构件的软件开发
软考高级系统架构设计师系列论文七十四:基于构件的软件开发 一、构件相关知识点二、摘要三、正文四、总结一、构件相关知识点 软考高级系统架构设计师系列之:面向构件的软件设计,构件平台与典型架构...

图为科技_边缘计算在智能安防领域的作用
边缘计算在智能安防领域发挥着重要的作用。智能安防系统通常需要处理大量的图像、视频和传感器数据,并对其进行实时分析和处理。边缘计算可以将计算和数据处理功能移动到离数据源更接近的地方,例如摄像头、传感器设备或安防终端。 以下是边缘计算在智能…...

Android 13 - Media框架(7)- NuPlayer::Source
Source 在播放器中起着拉流(Streaming)和解复用(demux)的作用,Source 设计的好坏直接影响到播放器的基础功能,我们这一节将会了解 NuPlayer 中的通用 Source(GenericSource)关注本地…...

MySql015——使用子查询
一、创建customers表 ######################## # Create customers table ######################## use study;CREATE TABLE customers (cust_id int NOT NULL AUTO_INCREMENT,cust_name char(50) NOT NULL ,cust_address char(50) NULL ,cust_city char…...

leetcode 355 设计推特
用链表存储用户发送的每一个推特,用堆获取最先的10条动态 class Twitter {Map<Integer,Set<Integer>> followMap;//规定最新的放到最后Map<Integer,Tweet> postMap;//优先队列(堆)PriorityQueue<Tweet> priorityQueue;int time…...

倒数 2 周|期待 2023 Google开发者大会
9 月 6-7 日,中国上海 前沿科技,新知同享 趣味体验,灵感齐聚 技术生态,多元共进 关注官网最新信息,敬请期待大会开幕 2023 Google 开发者大会官网 相信你一定记得,在今年 5 月的 Google I/O 大会上&am…...

代码随想录day57
516最长回文子序列 class Solution { public:int longestPalindromeSubseq(string s) {vector<vector<int>>dp(s.size(),vector<int>(s.size(),0));for(int i0;i<s.size();i)dp[i][i]1;for(int is.size()-1;i>0;i--){for(int ji1;j<s.size();j){if…...

YOLOv5、v8改进:CrissCrossAttention注意力机制
目录 1.简介 2. yolov5添加方法: 2.1common.py构建CrissCrossAttention模块 2.2yolo.py中注册 CrissCrossAttention模块 2.3修改yaml文件。 1.简介 这是ICCV2019的用于语义分割的论文,可以说和CVPR2019的DANet遥相呼应。 和DANet一样,…...

RabbitMQ特性介绍和使用案例
❤ 作者主页:李奕赫揍小邰的博客 ❀ 个人介绍:大家好,我是李奕赫!( ̄▽ ̄)~* 🍊 记得点赞、收藏、评论⭐️⭐️⭐️ 📣 认真学习!!!🎉🎉 文章目录 RabbitMQ特性…...

Ansible 使用 RHEL 系统角色
安装 RHEL 系统角色软件包,并创建符合以下条件的 playbook /home/greg/ansible/timesync.yml 在所有受管节点上运行 使用 timesync 角色 配置该角色,以使用当前有效的 NTP 提供商 配置该角色,以使用时间服务器 172.25.254.254 配置该角色&am…...

重新认识Android中的线程
线程的几种创建方式 new Thread:可复写Thread#run方法。也可以传递Runnable对象,更加灵活。缺点:缺乏统一管理,可能无限制新建线程,相互之间竞争,及可能占用过多系统的资源导致死机或oom。 new Thread(new…...

前端(十五)——GitHub开源一个react封装的图片预览组件
👵博主:小猫娃来啦 👵文章核心:GitHub开源一个react封装的图片预览组件 文章目录 组件开源代码下载地址运行效果展示实现思路使用思路和api实现的功能数据和入口部分代码展示 组件开源代码下载地址 Gitee:点此跳转下载…...

DELL Power Edge R740 安装 OracleLinux-R7-U9-Server
一、准备好 OracleLinux-R7-U9-Server-x86_64-dvd 安装介子: 二、通过 iDRAC挂dvd 安装介子 三、在 iDRAC 开机控制选择虚拟 CD/DCD/ISO 电源控制选择 复位系统(热启动) 四、进入安装阶段 五、配置时区 六、配置磁盘 七、删除之前的旧分区 …...

深入了解OpenStack:创建定制化QCOW2格式镜像的完全指南
OpenStack 创建自定义的QCOW2格式镜像 前言 建议虚机网络配置为 NAT 或 桥接,因为未来 KVM虚机 需要借助 虚机 的外网能力进行联网安装软件包 虚机在启动前,必须在 VMware Workstation 上为其开启虚拟化引擎 虚拟化 Intel VT-x/EPT 或 AMD-V 安装kvm …...

【Java 中级】一文精通 Spring MVC - 数据格式化器(六)
👉博主介绍: 博主从事应用安全和大数据领域,有8年研发经验,5年面试官经验,Java技术专家,WEB架构师,阿里云专家博主,华为云云享专家,51CTO 专家博主 ⛪️ 个人社区&#x…...

Linux内核学习(十二)—— 页高速缓存和页回写(基于Linux 2.6内核)
目录 一、缓存手段 二、Linux 页高速缓存 三、flusher 线程 Linux 内核实现了一个被叫做页高速缓存(page cache)的磁盘缓存,它主要用来减少对磁盘的 I/O 操作。它是通过把磁盘中的数据缓存到内存中,把对磁盘的访问变为对物理内…...

大数据-玩转数据-Flink窗口函数
一、Flink窗口函数 前面指定了窗口的分配器, 接着我们需要来指定如何计算, 这事由window function来负责. 一旦窗口关闭, window function 去计算处理窗口中的每个元素. window function 可以是ReduceFunction,AggregateFunction,or ProcessWindowFunction中的任意一种. Reduc…...

Docker网络-探索容器网络如何相互通信
当今世界,企业热衷于容器化,这需要强大的网络技能来正确配置容器架构,因此引入了 Docker Networking 的概念。Docker 是一种容器化平台,允许您在独立、轻量级的容器中运行应用程序和服务。Docker 提供了一套强大的网络功能&#x…...

ESP32-CAM模块Arduino环境搭建测试
ESP32-CAM模块Arduino环境搭建测试 一.ESP32OV2640摄像头模块CameraWebServer视频查看 二.测试ESP32-CAM(后续称cam模块)代码是否上传执行成功测试 const int led0 12; const int led1 13;void setup() {// put your setup code here, to run once:pinMode(led0, OUTPUT);pin…...

webassembly001 webassembly简述
WebAssembly 官方地址:https://webassembly.org/相关历史 https://en.wikipedia.org/wiki/WebAssembly https://brendaneich.com/2015/06/from-asm-js-to-webassembly/WebAssembly(缩写为Wasm)是一种基于堆栈的虚拟机的二进制指令格式。Wasm 被设计为编…...

vue 使用C-Lodop打印小票
先从官网下载js文件 https://www.lodop.net/LodopDemo.html 打开安装程序,一直下一步既可,我这边已经安装过就不演示了。 // 引入 import { getLodop } from /utils/CLodopfuncs.js;// 使用 let LODOP getLodop()let Count LODOP.GET_PRINTER_COUNT…...

【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现
💓博主CSDN主页:杭电码农-NEO💓 ⏩专栏分类:C从入门到精通⏪ 🚚代码仓库:NEO的学习日记🚚 🌹关注我🫵带你学习C 🔝🔝 vector 1. 前言2. 熟悉vector的接口函数2.1 vec…...

1. import pandas as pd 导入库
【目录】 文章目录 1. import pandas as pd 导入库1. pandas库的概念2. 导入pandas库2.1 常规导入2.2 别名导入 3. 别名的作用4. 课堂练习 【正文】 1. import pandas as pd 导入库 【学习时间】 10分钟 1. pandas库的概念 pandas:熊猫panda的复数, …...

DMK5框选变量之后不显示其他位置的此变量高亮
使用软件MDK5.3.8版本 如下在2的位置选择之后,其他同样的变量没有高亮,因为1的原因折叠了; 展开折叠之后就可以了...

0061__Appium
Appium Documentation - Appium Documentation APP自动化测试(3)-Appium Inspector介绍_六天测试工程师的博客-CSDN博客 https://github.com/appium/appium-inspector https://github.com/appium/appium-desktop https://github.com/appium/appium...