leetcode热题100.柱状图中最大的矩形

Problem: 84. 柱状图中最大的矩形

文章目录

  • 题目
  • 思路
  • 复杂度
  • Code

题目

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

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

示例 1:
在这里插入图片描述

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

示例 2:
在这里插入图片描述

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

思路

对于一根柱子x,其高为h.假如我们知道了他左边的第一根小于他的柱子的位置l和邮编第一个小于的高度的柱子r,那么我们很容易求得他的最大面积为: s = ( r − l − 1 ) ∗ h s = (r-l-1) * h s=(rl1)h

根据这一性质,我们采用单调栈的方法,在栈中保留第一个比当前元素小的元素的索引,所有大于当前元素的索引都将被弹出;如果栈不为空,说明存在这样一个索引,其对应的元素值小于当前元素,我们记录他。

我们分别从左往右和从右往左计算两遍,最后得出答案

复杂度

时间复杂度:

O ( n ) O(n) O(n)

空间复杂度:

O ( n ) O(n) O(n)

Code

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:n = len(heights)left = [-1] * nst = []for i,x in enumerate(heights):while st and heights[st[-1]] >= x:st.pop()if st:left[i] = st[-1]st.append(i)right = [n] * nst.clear()for i in range(n-1,-1,-1):x = heights[i]while st and heights[st[-1]] >= x:st.pop()if st:right[i] = st[-1]st.append(i)ans = 0for h,l,r in zip(heights,left,right):ans = max(ans,h*(r-l-1))return ans

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

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

相关文章

Qlib-Server:量化库数据服务器

Qlib-Server:量化库数据服务器 介绍 Qlib-Server 是 Qlib 的配套服务器系统,它利用 Qlib 进行基本计算,并提供广泛的服务器系统和缓存机制。通过 Qlib-Server,可以以集中的方式管理 Qlib 提供的数据。 框架 Qlib 的客户端/服务器框架基于 WebSocket 构建,这是因为 WebS…

OpenHarmony中的LLDB高性能调试器

概述 LLDB(Low Lever Debugger)是新一代高性能调试器。详细说明参考 LLDB官方文档 。 当前OpenHarmony中的LLDB工具是在 llvm15.0.4 基础上适配演进出来的工具,是HUAWEI DevEco Studio工具中默认的调试器,支持调试C和C应用。 工…

镜视界 | DevSecOps CI/CD 管道中数字供应链安全的集成策略

目录 前言 数字供应链(DSC)的定义 数字供应链安全的重点内容和风险因素 CI/CD管道的安全目标和可信实体 将数字供应链安全集成到CI/CD管道中 结语 本文字数:7715,阅读时长:19分钟 1.前言 在敏捷开发的模式下&…

SnapGene 5 for Mac 分子生物学软件

SnapGene 5 for Mac是一款专为Mac操作系统设计的分子生物学软件,以其强大的功能和用户友好的界面,为科研人员提供了高效、便捷的基因克隆和分子实验设计体验。 软件下载:SnapGene 5 for Mac v5.3.1中文激活版 这款软件支持DNA构建和克隆设计&…

StarRocks实战——多点大数据数仓构建

目录 前言 一、背景介绍 二、原有架构的痛点 2.1 技术成本 2.2 开发成本 2.2.1 离线 T1 更新的分析场景 2.2.2 实时更新分析场景 2.2.3 固定维度分析场景 2.2.4 运维成本 三、选择StarRocks的原因 3.1 引擎收敛 3.2 “大宽表”模型替换 3.3 简化Lambda架构 3.4 模…

目标检测的相关模型图:YOLO系列和RCNN系列

目标检测的相关模型图:YOLO系列和RCNN系列 前言YOLO系列的图展示YOLOpassthroughYOLO2YOLO3YOLO4YOLO5 RCNN系列的图展示有关目标检测发展的 前言 最近好像大家也都在写毕业论文,前段时间跟朋友聊天,突然想起自己之前写画了一些关于YOLO、Fa…

excel中批量插入分页符

excel中批量插入分页符,实现按班级打印学生名单。 1、把学生按照学号、班级排序好。 2、选择班级一列,点击数据-分类汇总。汇总方式选择计数,最后三个全部勾选。汇总结果一定要显示在数据的下发,如果显示在上方,后期…

实战|使用 Node.js 和 htmx 构建全栈应用程序

在本教程中,我将演示如何使用 Node 作为后端和 htmx 作为前端来构建功能齐全的 CRUD 应用程序。这将演示 htmx 如何集成到全栈应用程序中,使您能够评估其有效性并确定它是否是您未来项目的不错选择。 htmx 是一个现代 JavaScript 库,旨在通过…

系统架构图怎么画

画架构图是架构师的一门必修功课。 对于架构图是什么这个问题,我们可以按以下等式进行概括: 架构图 架构的表达 架构在不同抽象角度和不同抽象层次的表达,这是一个自然而然的过程。 不是先有图再有业务流程、系统设计和领域模型等&#…

项目四-图书管理系统

1.创建项目 流程与之前的项目一致,不再进行赘述。 2.需求定义 需求: 1. 登录: ⽤⼾输⼊账号,密码完成登录功能 2. 列表展⽰: 展⽰图书 3.前端界面测试 无法启动!!!--->记得加入mysql相关操作记得在yml进行配置 配置后启动…

基于ZHW3548的红外额温枪解决方案

红外额温枪,非接触式测量最典型的方法是红外测温。自红外辐射原理被发现以来,红外技术被广泛应用在温度测量中。红外测温仪具有测温范围广,响应速度快,灵敏度高等特点。红外耳温枪、红外额温计和红外筛检仪都属于非接触式体温计。…

admin端

一、创建项目 1.1 技术栈 1.2 vite 项目初始化 npm init vitelatest vue3-element-admin --template vue-ts 1.3 src 路径别名配置 Vite 配置 配置 vite.config.ts // https://vitejs.dev/config/import { UserConfig, ConfigEnv, loadEnv, defineConfig } from vite im…

C语言 C6031:返回值被忽略:“scanf“ 问题解决

我们在代码中 直接使用 scanf 就会出现这个错误 在最上面 加上 #define _CRT_SECURE_NO_WARNINGS//禁用安全函数警告 #pragma warning(disable:6031)//禁用 6031 的安全警告即可正常运行

TitanIDE与传统 IDE 比较

与传统IDE的比较 TitanIDE 和传统 IDE 属于不同时代的产物,在手工作坊时代,一切都是那么的自然,开发者习惯 Windows 或 MacOS 原生 IDE。不过,随着时代的变迁,软件行业已经步入云原生时代,TitanIDE 是顺应…

Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单实战案例 之九 简单闪烁效果

Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单实战案例 之九 简单闪烁效果 目录 Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单实战案例 之九 简单闪烁效果 一、简单介绍 二、简单闪烁效果实现原理 三、简单闪烁效果案例实现简单步骤 四、注意事项 一、简单…

JimuReport积木报表 v1.7.4 公测版本发布,免费的JAVA报表工具

项目介绍 一款免费的数据可视化报表,含报表和大屏设计,像搭建积木一样在线设计报表!功能涵盖,数据报表、打印设计、图表报表、大屏设计等! Web 版报表设计器,类似于excel操作风格,通过拖拽完成报…

多源统一视频融合可视指挥调度平台VMS/smarteye系统概述

系统功能 1. 集成了视频监控典型的常用功能,包括录像(本地录像、云端录像(录像计划、下载计划-无线导出)、远程检索回放)、实时预览(PTZ云台操控、轮播、多屏操控等)、地图-轨迹回放、语音对讲…

iptables添加端口映射,k8s主机查询不到端口但能访问。

研究原因:k8s内一台主机使用命令查询没有80端口。但通过浏览器访问又能访问到服务。 查询了资料是使用了hostport方式暴露pod端口。cni调用iptables增加了DNAT规则。访问时流量先经过iptables直接被NAT到具体服务去了。 链接: K8s罪魁祸首之"HostPort劫持了我…

Docker 夺命连环 15 问

目录 什么是Docker? Docker的应用场景有哪些? Docker的优点有哪些? Docker与虚拟机的区别是什么? Docker的三大核心是什么? 如何快速安装Docker? 如何修改Docker的存储位置? Docker镜像常…

使用certbot为网站启用https

1. 安装certbot客户端 cd /usr/local/bin wget https://dl.eff.org/certbot-auto chmod ax ./certbot-auto 2. 创建目录和配置nginx用于验证域名 mkdir -p /data/www/letsencryptserver {listen 80;server_name ~^(?<subdomain>.).ninvfeng.com;location /.well-known…