当前位置: 首页 > news >正文

代码随想录第50天 | 84.柱状图中最大的矩形

84.柱状图中最大的矩形

//双指针 js中运行速度最快
var largestRectangleArea = function(heights) {const len = heights.length;const minLeftIndex = new Array(len);const maxRigthIndex = new Array(len);// 记录每个柱子 左边第一个小于该柱子的下标minLeftIndex[0] = -1; // 注意这里初始化,防止下面while死循环for(let i = 1; i < len; i++) {let t = i - 1;// 这里不是用if,而是不断向左寻找的过程while(t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];minLeftIndex[i] = t;}// 记录每个柱子 右边第一个小于该柱子的下标maxRigthIndex[len - 1] = len; // 注意这里初始化,防止下面while死循环for(let i = len - 2; i >= 0; i--){let t = i + 1;// 这里不是用if,而是不断向右寻找的过程while(t < len && heights[t] >= heights[i]) t = maxRigthIndex[t];maxRigthIndex[i] = t;}// 求和let maxArea = 0;for(let i = 0; i < len; i++){let sum = heights[i] * (maxRigthIndex[i] - minLeftIndex[i] - 1);maxArea = Math.max(maxArea , sum);}return maxArea;
};//单调栈 
var largestRectangleArea = function(heights) {let maxArea = 0;const stack = [];heights = [0,...heights,0]; // 数组头部加入元素0 数组尾部加入元素0for(let i = 0; i < heights.length; i++){ // 只用考虑情况一 当前遍历的元素heights[i]小于栈顶元素heights[stack[stack.length-1]]]的情况while(heights[i] < heights[stack[stack.length-1]]){// 当前bar比栈顶bar矮const stackTopIndex = stack.pop();// 栈顶元素出栈,并保存栈顶bar的索引let w = i - stack[stack.length -1] - 1;let h = heights[stackTopIndex]// 计算面积,并取最大面积maxArea = Math.max(maxArea, w * h);}stack.push(i);// 当前bar比栈顶bar高了,入栈}return maxArea;
};

思路

跟雨水是反的

相关文章:

代码随想录第50天 | 84.柱状图中最大的矩形

84.柱状图中最大的矩形 //双指针 js中运行速度最快 var largestRectangleArea function(heights) {const len heights.length;const minLeftIndex new Array(len);const maxRigthIndex new Array(len);// 记录每个柱子 左边第一个小于该柱子的下标minLeftIndex[0] -1; //…...

深度学习---卷积神经网络

卷积神经网络概述 卷积神经网络是深度学习在计算机视觉领域的突破性成果。在计算机视觉领域。往往输入的图像都很大&#xff0c;使用全连接网络的话&#xff0c;计算的代价较高。另外图像也很难保留原有的特征&#xff0c;导致图像处理的准确率不高。 卷积神经网络&#xff0…...

Windows系统下安装CouchDB3.3.2教程

安装 前往CouchDB官网 官网点击download下载msi文件 双击该msi文件&#xff0c;一直下一步 创建个人account 设置cookie value 用于进行身份验证和授权。 愉快下载 点击OK 重启 启动 重启电脑后 打开浏览器并访问以下链接&#xff1a;http://127.0.0.1:5984/ 如果没有问…...

JavaScript基础知识(二)

JavaScript基础知识&#xff08;二&#xff09; 一、ES2015 基础语法1.变量2.常量3.模板字符串4.结构赋值 二、函数进阶1. 设置默认参数值2. 立即执行函数3. 闭包4. 箭头函数 三、面向对象1. 面向对象概述2. 基本概念3. 新语法 与 旧语法3.1 ES5 面向对象的知识ES5构造函数原型…...

SQL NULL Values(空值)

什么是SQL NULL值&#xff1f; SQL 中&#xff0c;NULL 用于表示缺失的值。数据表中的 NULL 值表示该值所处的字段为空。 具有NULL值的字段是没有值的字段。 如果表中的字段是可选的&#xff0c;则可以插入新记录或更新记录而不向该字段添加值。然后&#xff0c;该字段将被保存…...

云原生Docker网络管理

目录 Docker网络 Docker 网络实现原理 为容器创建端口映射 查看容器的输出和日志信息 Docker 的网络模式 查看docker网络列表 指定容器网络模式 网络模式详解 host模式 container模式 none模式 bridge模式 自定义网络 Docker网络 Docker 网络实现原理 Docker使用Lin…...

聊聊线程池的预热

序 本文主要研究一下线程池的预热 prestartCoreThread java/util/concurrent/ThreadPoolExecutor.java /*** Starts a core thread, causing it to idly wait for work. This* overrides the default policy of starting core threads only when* new tasks are executed. T…...

VueComponent的原型对象

一、prototype 每一个构造函数身上又有一个prototype指向其原型对象。 如果我们在控制台输入如下代码&#xff0c;就能看到Vue构造函数的信息&#xff0c;在他身上可以找到prototype属性&#xff0c;指向的是Vue原型对象&#xff1a; 二、__proto__ 通过构造函数创建的实例对…...

Redis不止能存储字符串,还有List、Set、Hash、Zset,用对了能给你带来哪些优势?

文章目录 &#x1f31f; Redis五大数据类型的应用场景&#x1f34a; 一、String&#x1f34a; 二、Hash&#x1f34a; 三、List&#x1f34a; 四、Set&#x1f34a; 五、Zset &#x1f4d5;我是廖志伟&#xff0c;一名Java开发工程师、Java领域优质创作者、CSDN博客专家、51CTO…...

Python OpenCV通过灰度平均值进行二值化处理以减少像素误差

Python OpenCV通过灰度平均值进行二值化处理以减少像素误差 前言前提条件相关介绍实验环境通过灰度平均值进行二值化处理以减少像素误差固定阈值二值化代码实现 灰度平均值二值化代码实现 前言 由于本人水平有限&#xff0c;难免出现错漏&#xff0c;敬请批评改正。更多精彩内容…...

[Golang]多返回值函数、defer关键字、内置函数、变参函数、类成员函数、匿名函数

函数 文章目录 函数多返回值函数按值传递、按引用传递类成员函数改变外部变量变参函数defer和追踪说明一些常见操作实现 使用defer实现代码追踪记录函数的参数和返回值 常见的内置函数将函数作为参数闭包实例闭包将函数作为返回值 计算函数执行时间使用内存缓存来提升性能 参考…...

【剑指Offer】:删除链表中的倒数第N个节点(此题是LeetCode上面的)剑指Offer上面是链表中的倒数第K个节点

给定一个链表&#xff0c;删除链表的倒数第 n 个结点&#xff0c;并且返回链表的头结点 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5], n 2 输出&#xff1a;[1,2,3,5] 示例 2&#xff1a; 输入&#xff1a;head [1], n 1 输出&#xff1a;[] 示例 3&#xff1a;…...

acwing第 126 场周赛 (扩展字符串)

5281. 扩展字符串 一、题目要求 某字符串序列 s0,s1,s2,… 的生成规律如下&#xff1a; s0 DKER EPH VOS GOLNJ ER RKH HNG OI RKH UOPMGB CPH VOS FSQVB DLMM VOS QETH SQBsnDKER EPH VOS GOLNJ UKLMH QHNGLNJ Asn−1AB CPH VOS FSQVB DLMM VOS QHNG Asn−1AB&#xff0c;其…...

Milvus 介绍

Milvus 介绍 Milvus 矢量数据库是什么&#xff1f;关键概念非结构化数据嵌入向量向量相似度搜索 为什么是 Milvus?支持哪些索引和指标&#xff1f;索引类型相似度指标(Similarity metrics) 应用示例Milvus 是如何设计的&#xff1f;开发者工具API访问Milvus 生态系统工具 本页…...

Linux绝对路径和相对路径

在 Linux 中&#xff0c;简单的理解一个文件的路径&#xff0c;指的就是该文件存放的位置。 只要我们告诉 Linux 系统某个文件存放的准确位置&#xff0c;那么它就可以找到这个文件。指明一个文件存放的位置&#xff0c;有 2 种方法&#xff0c;分别是使用绝对路径和相对路径。…...

Linux:firewalld防火墙-基础使用(2)

上一章 Linux&#xff1a;firewalld防火墙-介绍&#xff08;1&#xff09;-CSDN博客https://blog.csdn.net/w14768855/article/details/133960695?spm1001.2014.3001.5501 我使用的系统为centos7 firewalld启动停止等操作 systemctl start firewalld 开启防火墙 systemct…...

【每日一练】20231023

统计每个字符出现的次数相关问题 方法一&#xff1a;map的put方法遍历 public class Test {public static void main(String[] args) {StringBuilder sb new StringBuilder("");Random ran new Random();for(int i0;i<2000000;i) {sb.append((char) (a ran.n…...

【项目经理】工作流引擎

项目经理之 工作流引擎 一、业务系统管理目的维护信息 二、组织架构管理目的维护信息 三、角色矩阵管理目的维护信息 四、条件变量管理目的维护信息 五、流程模型管理目的维护信息 六、流程版本管理目的维护信息 七、流程监管控制目的维护信息 系列文章版本记录 一、业务系统管…...

025-第三代软件开发-实现需求长时间未操作返回登录界面

第三代软件开发-实现需求长时间未操作返回登录界面 文章目录 第三代软件开发-实现需求长时间未操作返回登录界面项目介绍实现需求长时间未操作返回登录界面实现思路用户操作监控QML 逻辑处理 关键字&#xff1a; Qt、 Qml、 QTimer、 timeout、 eventFilter 项目介绍 欢迎…...

驱动开发LED灯绑定设备文件

头文件 #ifndef __HEAD_H__ #define __HEAD_H__typedef struct {unsigned int MODER;unsigned int OTYPER;unsigned int OSPEEDR;unsigned int PUPDR;unsigned int IDR;unsigned int ODR; }gpio_t;#define PHY_LED1_ADDR 0x50006000 #define PHY_LED2_ADDR 0x50007000 #defin…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

向量几何的二元性:叉乘模长与内积投影的深层联系

在数学与物理的空间世界中&#xff0c;向量运算构成了理解几何结构的基石。叉乘&#xff08;外积&#xff09;与点积&#xff08;内积&#xff09;作为向量代数的两大支柱&#xff0c;表面上呈现出截然不同的几何意义与代数形式&#xff0c;却在深层次上揭示了向量间相互作用的…...

验证redis数据结构

一、功能验证 1.验证redis的数据结构&#xff08;如字符串、列表、哈希、集合、有序集合等&#xff09;是否按照预期工作。 2、常见的数据结构验证方法&#xff1a; ①字符串&#xff08;string&#xff09; 测试基本操作 set、get、incr、decr 验证字符串的长度和内容是否正…...

二叉树-144.二叉树的前序遍历-力扣(LeetCode)

一、题目解析 对于递归方法的前序遍历十分简单&#xff0c;但对于一位合格的程序猿而言&#xff0c;需要掌握将递归转化为非递归的能力&#xff0c;毕竟递归调用的时候会调用大量的栈帧&#xff0c;存在栈溢出风险。 二、算法原理 递归调用本质是系统建立栈帧&#xff0c;而非…...

【Vue】scoped+组件通信+props校验

【scoped作用及原理】 【作用】 默认写在组件中style的样式会全局生效, 因此很容易造成多个组件之间的样式冲突问题 故而可以给组件加上scoped 属性&#xff0c; 令样式只作用于当前组件的标签 作用&#xff1a;防止不同vue组件样式污染 【原理】 给组件加上scoped 属性后…...

Yolo11改进策略:Block改进|FCM,特征互补映射模块|AAAI 2025|即插即用

1 论文信息 FBRT-YOLO&#xff08;Faster and Better for Real-Time Aerial Image Detection&#xff09;是由北京理工大学团队提出的专用于航拍图像实时目标检测的创新框架&#xff0c;发表于AAAI 2025。论文针对航拍场景中小目标检测的核心难题展开研究&#xff0c;重点解决…...

TMC2226超静音步进电机驱动控制模块

目前已经使用TMC2226量产超过20K,发现在静音方面做的还是很不错。 一、TMC2226管脚定义说明 二、原理图及下载地址 一、TMC2226管脚定义说明 引脚编号类型功能OB11电机线圈 B 输出 1BRB2线圈 B 的检测电阻连接端。将检测电阻靠近该引脚连接到地。使用内部检测电阻时,将此引…...

Ansys Maxwell:线圈和磁体的静磁 3D 分析

本博客展示了如何在 Ansys Maxwell 中执行静磁 3D 分析&#xff0c;以计算载流线圈和永磁体之间相互作用产生的扭矩。在这个例子中&#xff0c;线圈中的电流产生一个沿 Y 轴指向的磁场&#xff0c;而永磁体沿 X 轴被磁化。这种配置导致围绕 Z 轴的扭矩。分步工作流程包括构建几…...