【LeetCode】84.柱状图中最大的矩形

题目

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

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

示例 1:

输入:heights = [2,1,5,6,2,3]
输出:10
解释:最大的矩形为图中红色区域,面积为 10

示例 2:

输入: heights = [2,4]
输出: 4

提示:

  • 1 <= heights.length <=10^5
  • 0 <= heights[i] <= 10^4

解答

源代码

class Solution {public int largestRectangleArea(int[] heights) {int[] left = new int[heights.length];int[] right = new int[heights.length];Deque<Integer> stack = new ArrayDeque<>();for (int i = 0; i < heights.length; i++) {while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {stack.pop();}left[i] = (stack.isEmpty() ? -1 : stack.peek());stack.push(i);}stack.clear();for (int i = heights.length - 1; i > -1; i--) {while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {stack.pop();}right[i] = (stack.isEmpty() ? heights.length : stack.peek());stack.push(i);}int res = 0;for (int i = 0; i < heights.length; i++) {res = Math.max(res, (right[i] - left[i] - 1) * heights[i]);}return res;}
}

总结

最大矩形的高度一定是某个柱子的高度,所以我们只要把每个柱子的高度往两边延伸,记录下它们能达到的最大的宽度,计算出矩形面积。

利用暴力枚举虽然也能找到某个柱子两边小于它且离它最近的柱子,但这明显不太优雅,肯定不是最佳解法。

为了跳过不必要的比较,我们所需要用到的就是“单调栈”。栈中存放的是柱子对应的下标,从栈底到栈顶,下标单调递增,下标对应的柱子高度也单调递增。从左到右遍历到某个柱子时,要用它和栈顶下标对应的柱子高度比较,如果低于等于栈顶对应柱子,就出栈直到该柱子高于栈顶对应柱子,那么此时栈顶下标对应的柱子就是当前柱子左边小于它且离它最近的柱子。同理,得到右边的。

这样经过两次遍历,我们可以得到每个柱子左右两边的边界。这里有特殊情况,如果左右两边没有比自己低的柱子,那就将边界设为0 / heights.length。然后计算出以每个柱子高度为矩形高度得到的矩形面积,比较选出最大的面积。

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

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

相关文章

python+selenium自动化测试项目实战

说明&#xff1a;本项目采用流程控制思想&#xff0c;未引用unittest&pytest等单元测试框架 一.项目介绍 目的 测试某官方网站登录功能模块可以正常使用 用例 1.输入格式正确的用户名和正确的密码&#xff0c;验证是否登录成功&#xff1b; 2.输入格式正确的用户名和不…

C++ Opencv视频检测

使用OpenCV进行视频检测的一般步骤如下&#xff1a;导入OpenCV库和视频文件。 对每一个视频帧进行对象检测。可以使用诸如Haar特征分类器、Cascade分类器或深度学习模型等技术进行对象检测。 #include <opencv2/imgcodecs.hpp> #include <opencv2/highgui.hpp> …

安防视频监控/视频汇聚平台EasyCVR服务重启,海康SDK设备无法上线是什么原因?

TSINGSEE青犀视频监控汇聚平台EasyCVR可拓展性强、视频能力灵活、部署轻快&#xff0c;可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等&#xff0c;以及支持厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等。旭帆科技平台既具备传统安防视频监控…

MybatisPlus框架教程:入门、条件构造器、接口操作、代码生成器

MybatisPlus框架 文章目录 MybatisPlus框架快速上手条件构造器接口基本操作新版代码生成器 前面我们体验了JPA带来的快速开发体验&#xff0c;但是我们发现&#xff0c;面对一些复杂查询时&#xff0c;JPA似乎有点力不从心&#xff0c;反观稍微麻烦一点的Mybatis却能够手动编写…

el-dialog设置高度、使用resetFields清除表单项无效问题

初学者容易踩坑的的el-dialog、el-form问题 1. el-dialog设置高度2. el-form中表单项对不齐3. 使用resetFields清除表单项无效 1. el-dialog设置高度 在el-dialog中里面添加一个div设置固定高度&#xff0c;或者限制最小的高度。 <el-dialogtitle"选择图标"v-mod…

数据结构 - 单链表

文章目录 目录 文章目录 一、什么是链表? 线性表: 顺序表: 二、链表的分类和实现 分类: 实现: 1.创建节点类 2.创建单链表 1.addTail(尾增) 2.删除节点值为key的第一个节点 3.插入节点(在指定位置) 4.获取链表长度 总结 前言 大家好,这篇博客给大家讲一下什么是…

『虫无涯→_→读书推荐02期』|全面系统的〖Effective软件测试〗带你完成所有不同类型的测试,GO

目录 我看的书 我的书评/推荐理由 书籍的作者 书籍内容 赠书活动 我看的书 首次看到这本书的封面的时候&#xff0c;我被那个数字惊呆了&#xff0c;【助理软件研发提升10倍质量】&#xff0c;这对我产生了足够了吸引力。因为这个数字是非常的客观的&#xff1b;至于书…

Matlab信号处理2:方波信号的合成与分解

周期信号可展开为傅里叶级数&#xff0c;因此方波信号可用若干谐波去拟合。以下是Matlab的实现&#xff1a; %% 方波信号的分解% 1.生成方波信号 % 方波信号周期、基波频率 T0 2; w0 (2 * pi) / T0; % 方波信号值为1的区间 T1 0.5; % 绘图周期&#xff1a;(2*n1)个周期 n …

化繁为简 面板式空调网关亮相上海智能家居展 智哪儿专访青岛中弘赵哲海

面对中央空调协议不开放和智能家居协议不统一的问题&#xff0c;青岛中弘选择中央空调控制器这一细分赛道入局智能家居市场&#xff0c;始终贯彻“所有空调&#xff0c;一个网关”的产品技术理念&#xff0c;逐渐探索出一条中弘的发展路径和商业模式。 在2023年的SSHT上海国际智…

【css】z-index与层叠上下文

z-index属性用来设置元素的堆叠顺序&#xff0c;使用z-index有一个大的前提&#xff1a;z-index所作用元素的样式列表中必须有position属性并且属性值为absolute、relative或fixed中的一个&#xff0c;否则z-index无效。 层叠上下文 MDN讲解 我们给元素设置的z-index都是有一…

MPDIoU: A Loss for Efficient and Accurate Bounding BoxRegression

MPDIoU: A Loss for Efficient and Accurate Bounding BoxRegression MPDIoU:一个有效和准确的边界框损失回归函数 摘要 边界框回归(Bounding box regression, BBR)广泛应用于目标检测和实例分割&#xff0c;是目标定位的重要步骤。然而&#xff0c;当预测框与边界框具有相同的…

Qt---对话框 事件处理 如何发布自己写的软件

目录 一、对话框 1.1 消息对话框&#xff08;QMessageBox&#xff09; 1> 消息对话框提供了一个模态的对话框&#xff0c;用来提示用户信息&#xff0c;或者询问用户问题并得到回答 2> 基于属性版本的API 3> 基于静态成员函数版本 4> 对话框案例 1、ui界面 …

visual studio 2008 编译项目出现层次不穷问题枚举

文章目录 1、严重性 代码 说明 项目 文件 行 禁止显示状态 错误 C1047 对象或库文件“.lib”是使用与其他对象(如“x64\Release\main.obj”)不同的1、错误原因 2、意外的预编译头错误,只需重新运行编译器就可能修复此问题3、 warning LNK4099: 未找到 PDB“vc90.pdb”(使用“..…

微信小程序案例2-1:学生信息

文章目录 一、运行效果二、涉及知识点&#xff08;一&#xff09;常用组件1、view组件2、image组件 &#xff08;二&#xff09;rpx单位1、什么rpx单位2、rpx与px相互换算 三、实现步骤&#xff08;一&#xff09;创建项目&#xff08;二&#xff09;准备图像素材&#xff08;三…

测试需求分析

什么是软件测试需求&#xff1a; 灰度测试&#xff1a;先发布部分功能&#xff0c;然后看用户的反馈&#xff0c;再去发布另外一部分的更新 A/B测试&#xff1a;先发布的功能先让A部分的用户进行更新&#xff0c;再根据用户的犯困再更新B用户的功能 需求测试&#xff1a; 功…

Nginx从安装到使用,反向代理,负载均衡

什么是Nginx&#xff1f; 文章目录 什么是Nginx&#xff1f;1、Nginx概述1.1、Nginx介绍1.2、Nginx下载和安装1.3、Nginx目录结构 2、Nginx命令2.1、查看版本2.2、检查配置文件正确性2.3、启动和停止2.4、重新加载配置文件2.5、环境变量的配置 3、Nginx配置文件结构4、Nginx具体…

Spring依赖注入

Spring两大特性&#xff1a;IOC控制反转、AOP面向切面编程。 IOC&#xff1a;控制反转&#xff0c;把创建对象的过程交给 Spring 进行管理&#xff08;DI&#xff1a;依赖注入&#xff0c;在IoC容器内将有依赖关系的bean进行关系绑定。成员变量有两种注入方式&#xff1a;set注…

华为云云服务器评测|云耀云服务器L实例快速部署MySQL使用指南

文章目录 前言云耀云服务器L实例介绍什么是云耀云服务器L实例&#xff1f;产品优势智能不卡顿价优随心用上手更简单管理更省心 快速购买查看优惠卷购买 安装MySQL重置密码安装更新apt的软件源列表安装MySQL 设置用户名、密码、权限配置安全组 总结 前言 哈喽大家好&#xff0c…

Xcode,swift:Error Domain=kCLErrorDomain Code=1 (null)问题解决

问题描述: iOS开发时,当使用用户的位置权限时,获取用户经纬度报错:Error DomainkCLErrorDomain Code1 "(null)",错误域kCLError域代码1“(null)” 解决方法: 打开模拟机的设置-通用-语言与地区 将地区设置为中国(如果你的开发位置在中国的话) 点击左上方Features,选择…

ES6中的箭头函数(arrow function)与普通函数的不同之处

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 语法简洁⭐ 没有自己的this⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅&#xff01;这个专栏是为那些对Web开发感兴趣、…