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

题目

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

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

方法

代码:

class Solution {public int largestRectangleArea(int[] hs) {int n = hs.length;int[] l = new int[n], r = new int[n];Arrays.fill(l, -1); Arrays.fill(r, n);Deque<Integer> d = new ArrayDeque<>();// 遍历填充 r 数组, r[i]表示位置 i 右边最近一个比其小的位置for (int i = 0; i < n; i++) {while (!d.isEmpty() && hs[d.peekLast()] > hs[i]) r[d.pollLast()] = i;d.addLast(i);}d.clear(); // 处理完 r 数组, 清空栈// 遍历填充 l 数组, l[i]表示位置 i 左边最近一个比其小的位置for (int i = n - 1; i >= 0; i--) {while (!d.isEmpty() && hs[d.peekLast()] > hs[i]) l[d.pollLast()] = i;d.addLast(i);}int ans = 0;for (int i = 0; i < n; i++) {int t = hs[i], a = l[i], b = r[i];ans = Math.max(ans, (b - a - 1) * t);}return ans;}
}

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

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

相关文章

成为AI产品经理——模型评估概述

目录 一、模型宣讲和评估的原因 二、模型宣讲 三、模型评估 1. 重要特征 ① 特征来源 ②特征意义 2.选择测试样本 3.模型性能和稳定性 一、模型宣讲和评估的原因 刘海丰老师提到他们在做一个金融AI产品未注重模型指标&#xff0c;过于注重业务指标&#xff0c;导致产生…

Python小知识

个人学习笔记&#xff0c;用于记录使用过程中好用的技巧、好用的库。 1 小知识 1.1 相对路径 1.2 打包Exe文件 命令&#xff1a; pyinstaller -F main.py其中-F&#xff1a;覆盖之前打包的文件 mian.py&#xff1a;需要打包的Python文件 PS&#xff1a;使用pyinstaller 5.1…

Docker,从入门到精通

1、DockerFile 介绍 dockerfile 是啥?dockerfile 用来构建 docker 镜像的文件。 具体步骤&#xff1a; 1、编写一个 dockerfile 文件 2、docker build 构造一个镜像 3、docker run 运行镜像 4、docker push 发布镜像 DockerFile 构建过程 1、每个保留关键字都必须是大…

人工智能-优化算法之凸集

凸性 凸性&#xff08;convexity&#xff09;在优化算法的设计中起到至关重要的作用&#xff0c; 这主要是由于在这种情况下对算法进行分析和测试要容易。 换言之&#xff0c;如果算法在凸性条件设定下的效果很差&#xff0c; 那通常我们很难在其他条件下看到好的结果。 此外&…

【Vue】绝了!还有不懂生命周期的?

生命周期 Vue.js 组件生命周期&#xff1a; 生命周期函数&#xff08;钩子&#xff09;就是给我们提供了一些特定的时刻&#xff0c;让我们可以在这个周期段内加入自己的代码&#xff0c;做一些需要的事情; 生命周期钩子中的this指向是VM 或 组件实例对象 在JS 中&#xff0c;…

微服务实战系列之Cache

前言 欢迎来到Cache&#xff08;缓存&#xff09;的世界&#xff01; 自从世界第一台计算机诞生之日起&#xff0c;人们对效率的渴望逐步增强。从CPU到存储&#xff0c;从芯片到内存&#xff0c;一批又一批的先驱以一种孜孜不倦的“工匠”精神&#xff0c;为计算机运行效率的提…

华为P40无法链接adb的解决记录

真的很讨厌华为的设备&#xff0c;很多东西啥设备都能跑得好好的&#xff0c;就华为会出问题&#xff0c;简直就是手机界的IE。 情况&#xff1a;突然无法链接adb到P40&#xff0c;拔插无效&#xff0c;关闭开发人员选项再打开也无效&#xff0c;撤销USB调试授权也无效&#x…

西南科技大学电路分析基础实验A1(一阶电路的设计)

目录 一、实验目的 二、实验设备 三、预习内容(如:基本原理、电路图、计算值等) 四、实验数据及结果分析(预习写必要实验步骤和表格) 1. 观测一阶电

leetcode:有效的括号

题目描述 题目链接&#xff1a;20. 有效的括号 - 力扣&#xff08;LeetCode&#xff09; 题目分析 题目给了我们三种括号&#xff1a;&#xff08;&#xff09;、{ }、[ ] 这里的匹配包括&#xff1a;顺序匹配和数量匹配 最优的思路就是用栈来解决&#xff1a; 括号依次入栈…

用于计算机屏幕安全摄像头系统:Screen Anytime Crack

Screen Anytime 是一款软件&#xff0c;旨在自动将整个用户会话或 PC/服务器/VM/Kiosk 的 /RDP/Citrix/RemoteApp 会话的屏幕活动记录到视频日志文件中&#xff0c;以用于记录、审核和监控目的。通过重播其高度压缩的视频&#xff0c;您可以轻松回顾单台计算机或一组服务器/PC …

Joint Bilateral Upsampling

Abstract 图像分析和增强任务&#xff08;例如色调映射、着色、立体深度和蒙太奇&#xff09;通常需要在像素网格上计算解决方案&#xff08;例如&#xff0c;曝光、色度、视差、标签&#xff09;。计算和内存成本通常要求在下采样图像上运行较小的解决方案。尽管通用上采样方…

只需十分钟快速入门Python,快速了解基础内容学习。零基础小白入门适用。

文章目录 简介特点搭建开发环境版本hello world注释文件类型变量常量数据类型运算符和表达式控制语句数组相关函数相关字符串相关文件处理对象和类连接mysql关于Python技术储备一、Python所有方向的学习路线二、Python基础学习视频三、精品Python学习书籍四、Python工具包项目源…

matlab绘图函数plot和fplot的区别

一、背景 有的函数用plot画就会报错&#xff0c;显示数据必须为可转换为双精度值的数值、日期时间、持续时间、分类或数组。 如下图所示&#xff1a; 但用fplot函数就没有问题&#xff0c;因此这里记录一下两者的区别&#xff0c;如果使用不当&#xff0c;画出的图可能就是下…

以太网通讯协议小结--持续更新中

一、以太网介绍 以太网是一种产生较早&#xff0c;使用相当广泛的局域网技术&#xff0c;局域网就是一个区域的网络互联&#xff0c;可以使办公室也可以是学校等等&#xff0c;大小规模不一。 目前以太网根据速度等级分类大概分为&#xff1a;标准以太网&#xff08;10Mbit/s…

Redis-Redis高可用集群之水平扩展

Redis3.0以后的版本虽然有了集群功能&#xff0c;提供了比之前版本的哨兵模式更高的性能与可用性&#xff0c;但是集群的水平扩展却比较麻烦&#xff0c;今天就来带大家看看redis高可用集群如何做水平扩展&#xff0c;原始集群(见下图)由6个节点组成&#xff0c;6个节点分布在三…

JOSEF 双可调漏电继电器 ZLR-T81 ZCT-80 面板嵌入式安装

ZLR-T系列漏电继电器&#xff08;以下简称继电器&#xff09;适用于交流电压为380.660V.至1140V系统中源率为50HZ电流为15~4000A线路中做有无中性点漏电保护. 系列型号 ZLR-T81漏电继电器 ZLR-T81ZCT-35漏电继电器 ZLR-T81ZCT-80漏电继电器 ZLR-T81ZCT-120漏电继电器 一、…

csv文件EXCEL默认打开乱码问题

这里讨论的问题是&#xff0c;当用记事本打开带有中文字符的csv正常时&#xff0c;用excel打开却是乱码。 简单概括就是&#xff1a;编码问题&#xff0c;windows的 excel打开csv文本文件时&#xff0c;默认使用的是系统内的ANSI&#xff0c;在中文环境下就是GB2312。如果写文件…

华为ospf和isis双点双向路由重分布的次优路径和环路终极解决方案

r5上直接导入直连路由 r3和r2进行双点双向路由重分布 查看R3去往R5产生了次优路径&#xff1a; 因为是R2先互相引入的isis和ospf&#xff0c;所以R3会产生次优路径&#xff0c;如果是R3先相互引入ospf和isis&#xff0c;那就是R2去R5会产生次优路径&#xff0c;而R3本身不会。…

Spark_Spark高阶特性

wscg filter导致断链 Codegen 向量化 simdjson Orc Parquet 支持批量读取 spark本身对parquet支持比较好&#xff0c;因为parquet

基于FPGA的五子棋游戏设计

基于FPGA的五子棋游戏设计 本文基于FPGA设计五子棋游戏&#xff0c;使用按键输入&#xff0c;使用VGA接口输出。五子棋的棋具与围棋相同&#xff0c;棋子分为黑白两色&#xff0c;棋盘为1010&#xff0c;棋子放置于棋盘线交叉点上。两人对局&#xff0c;各执一色&#xff0c;轮…