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

代码随想录算法训练营第60天| Leetcode 84.柱状图中最大的矩形

文章目录

    • Leetcode 84.柱状图中最大的矩形

Leetcode 84.柱状图中最大的矩形

题目链接:Leetcode 84.柱状图中最大的矩形
题目描述: 给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。求在该柱状图中,能够勾勒出来的矩形的最大面积。

思路: 我们发现:数组中的每个元素,若假定以它为高,能够展开的宽度越宽,那么以它为高的矩形面积就越大。因此需要找到每个元素左边第一个比它矮的矩形和右边第一个比它矮的矩形,在这中间的就是最大宽度。 与Leetcode 42. 接雨水不同的是,本题的单调栈顺序:栈头到栈底从大到小。

代码如下:

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int result = 0;stack<int> st;// 将数组首尾加上0,避免因为栈空而跳过计算逻辑heights.insert(heights.begin(), 0);heights.push_back(0);st.push(0); // 栈内存放下标for (int i = 1; i < heights.size(); i++) {if (heights[i] >= heights[st.top()]) {st.push(i);} else {while (!st.empty() && heights[i] < heights[st.top()]) {int mid = st.top();st.pop();if (!st.empty()) {int l = st.top();int r = i;int w = r - l - 1;int h = heights[mid];result = max(result, w * h);}}st.push(i);}}return result;}
};

当我们对单调栈代码逻辑熟悉之后,刷题时可以直接依照模板来写:

stack<int> st;
for(int i = 0; i < nums.size(); i++)
{while(!st.empty() && st.top() > nums[i]){st.pop();}st.push(nums[i]);
}

总结: 单调栈还需要多刷题,仅仅掌握几道经典题目是不够的。

最后,如果文章有错误,请在评论区或私信指出,让我们共同进步!

相关文章:

代码随想录算法训练营第60天| Leetcode 84.柱状图中最大的矩形

文章目录 Leetcode 84.柱状图中最大的矩形 Leetcode 84.柱状图中最大的矩形 题目链接&#xff1a;Leetcode 84.柱状图中最大的矩形 题目描述&#xff1a; 给定 n 个非负整数&#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻&#xff0c;且宽度为 1 。求在该柱状…...

编写一个简单的cmakelist.txt

文章目录 代码main.cpp头文件和子模块CMakeLists.txtsubModule/CMakeLists.txt顶层CMakeLists.txtCMakeList中的内容说明生成跨平台到Visual studio下上一篇提到了cmake的设计目的与作用,这一篇就来手动编写一个基本的cmakelist.txt,并演示一下如何生成不同平台的构建文件。 …...

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的零售柜商品检测软件(Python+PySide6界面+训练代码)

摘要&#xff1a;开发高效的零售柜商品识别系统对于智能零售领域的进步至关重要。本文深入介绍了如何运用深度学习技术开发此类系统&#xff0c;并分享了全套实现代码。系统采用了领先的YOLOv8算法&#xff0c;并与YOLOv7、YOLOv6、YOLOv5进行了性能比较&#xff0c;呈现了诸如…...

数据库的学习

数据库软件&#xff1a; 关系型数据库&#xff1a;Mysql Oracle SqlServer Sqlite 非关系型数据库&#xff1a;Redis NoSQL 1.数组&#xff0c;链表&#xff0c;文件&#xff0c;数据库 数组&#xff0c;链表&#xff1a;内存存放数据的方式&…...

matlab去除图片上的噪声

本问题来自CSDN-问答板块,题主提问。 如何利用matlab去除图片上的噪声? 一、运行效果图 左边是原图,右边是去掉噪音后的图片。 二、中文说明 中值滤波是一种常见的图像处理技术,用于去除图像中的噪声。其原理如下: 1. 滤波器移动:中值滤波器是一个小的窗口,在图像上移…...

C++超详细知识点(五):类的友元函数和友元类

目录 标题&#xff1a; 友元函数和友元类1. 友元函数2. 友元类 标题&#xff1a; 友元函数和友元类 友元函数和友元类是C中的概念&#xff0c;它们允许某些函数或类访问另一个类的私有成员。这样的访问权限超过了通常的私有和保护访问级别。请注意&#xff0c;友元类的使用应该…...

SOC设计:关于reset的细节

有如下几个信号 1、时钟&#xff1a;clk_top 2、总的reset信号&#xff1a;rstn_top 3、scan的reset信号&#xff1a;scan_rstn 4、软件复位信号&#xff1a;rstn_soft_sub 5、scan模式信号&#xff1a;scan_mode 6、reset bypass 信号&#xff1a;scan_rstn_sel 功能&a…...

支小蜜AI校园防欺凌系统可以使用在宿舍吗?

随着人工智能技术的快速发展&#xff0c;AI校园防欺凌系统已成为维护校园安全的重要手段。然而&#xff0c;关于这一系统是否适用于宿舍环境&#xff0c;仍存在一些争议和讨论。本文将探讨AI校园防欺凌系统在宿舍中的适用性&#xff0c;分析其潜在的优势与挑战&#xff0c;并提…...

外卖平台订餐流程架构的实践

当我们想要在外卖平台上订餐时&#xff0c;背后其实涉及到复杂的技术架构和流程设计。本文将就外卖平台订餐流程的架构进行介绍&#xff0c;并探讨其中涉及的关键技术和流程。 ## 第一步&#xff1a;用户端体验 用户通过手机应用或网页访问外卖平台&#xff0c;浏览菜单、选择…...

[AIGC] Spring Boot中的切面编程和实例演示

切面编程&#xff08;Aspect Oriented Programming&#xff0c;AOP&#xff09;是Spring框架的关键功能之一。通过AOP&#xff0c;我们可以将代码下沉到多个模块中&#xff0c;有助于解决业务逻辑和非业务逻辑耦合的问题。本文将详细介绍Spring Boot中的切面编程&#xff0c;并…...

各个类型和Json类型的相互转换

ObjectMapper类(com.fasterxml.jackson.databind.ObjectMapper)是Jackson的主要类&#xff0c;它可以帮助我们快速的进行各个类型和Json类型的相互转换。 对应maven&#xff1a; <dependency><groupId>com.fasterxml.jackson.core</groupId><artifactId&…...

C语言:操作符详解(下)

目录 一、逗号表达式二、下标访问[ ]、函数调用()1. [ ]下标引用操作符2.函数调用操作符 三、结构成员访问操作符1.结构体(1) 结构的声明(2) 结构体变量的定义和初始化 2.结构成员访问操作符(1)结构体成员的直接访问(2)结构体成员的间接访问 四、操作符的属性&#xff1a;优先级…...

电商场景下 ES 搜索引擎的稳定性治理实践

继上文在完成了第一阶段 ES 搜索引擎的搭建后&#xff0c;已经能够实现对千万级别的商品索引的读写请求的支持。目前&#xff0c;单机房读流量在 500&#xff5e;1000 QPS 之间&#xff0c;写流量在 500 QPS 左右。 但随着业务的发展&#xff0c;问题也逐渐开始暴露&#xff0…...

jdk8与jdk17的区别。springboot2.x与springboot3.x的区别

1. jdk8与jdk17的区别 Java JDK 8 和 JDK 17 之间存在许多区别&#xff0c;包括功能、性能、语言特性和工具等方面。以下是它们之间的一些主要区别&#xff1a; 功能和语言特性&#xff1a; JDK 8引入了许多重要的语言特性&#xff0c;包括Lambda表达式、方法引用、Stream API、…...

Pytest测试中的临时目录与文件管理!

在Pytest测试框架中&#xff0c;使用临时目录与文件是一种有效的测试管理方式&#xff0c;它能够确保测试的独立性和可重复性。在本文中&#xff0c;我们将深入探讨如何在Pytest中利用临时目录与文件进行测试&#xff0c;并通过案例演示实际应用。 为什么需要临时目录与文件&a…...

arduino 编程esp8266

概述&#xff1a; 1.板子外设资源的访问&#xff1a;Libraries - Arduino Reference 注意&#xff1a;开发板未nodeMCU1.0(esp-12e)(esp8266-01s上调试的。) 2.硬件接线 en,vcc接3.3v,gnd接地&#xff08;也就是和串口共地&#xff09;&#xff0c;gpio1接地。tx接串口rx,rx接串…...

基于springboot实现数据资产管理系统项目【项目源码+论文说明】计算机毕业设计

基于springboot实现数据资产管理系统演示 摘要 固定资产管理系统主要是完成对系统用户管理、资产信息管理、资产变更管理、资产用途管理、资产类别管理和资产增减管理。因为利用本系统管理员可以直接录入信息&#xff0c;修改信息&#xff0c;删除信息&#xff0c;并且若在录入…...

在Java中如何将十进制转换为二进制,八进制,十六进制以及它们之间的互相转换

目录 一、算法实现进制之间的转换 &#xff08;1&#xff09;十进制转换为二进制 &#xff08;2&#xff09;二进制转换成十进制 二、Java中的API实现进制转换 &#xff08;1&#xff09;十进制转换为二进制 &#xff08;2&#xff09;十进制转换为八进制 &#xff08;3…...

AK/SK加密认证

一、AK/SK概念 Access Key (AK)&#xff1a;AK是一个全局唯一的字符串标识符&#xff0c;用于标识用户。它类似于用户名&#xff0c;但仅用于身份识别&#xff0c;并不包含任何秘密信息。 Secret Access Key (SK)&#xff1a;SK则是一个高度保密的密钥&#xff0c;类似于密码&…...

前端实现websocket通信讲解(vue2框架)

websocket&#xff1a; WebSocket是HTML5下一种新的协议&#xff08;websocket协议本质上是一个基于tcp的协议&#xff09;它实现了浏览器与服务器全双工通信&#xff0c;能更好的节省服务器资源和带宽并达到实时通讯的目的Websocket是一个持久化的协议 websocket提供的api&a…...

DDrawCompat:老游戏兼容性修复与性能优化终极解决方案

DDrawCompat&#xff1a;老游戏兼容性修复与性能优化终极解决方案 【免费下载链接】DDrawCompat DirectDraw and Direct3D 1-7 compatibility, performance and visual enhancements for Windows Vista, 7, 8, 10 and 11 项目地址: https://gitcode.com/gh_mirrors/dd/DDrawC…...

影墨·今颜GPU算力适配:RTX 4090单卡实测每秒1.8张1024x1536图

影墨今颜GPU算力适配&#xff1a;RTX 4090单卡实测每秒1.8张1024x1536图 1. 引言&#xff1a;当顶级AI影像遇上顶级显卡 如果你是一位内容创作者&#xff0c;或者对AI生成人像有浓厚兴趣&#xff0c;那么“影墨今颜”这个名字最近可能已经进入了你的视野。它被描述为一款融合…...

基于ELK的口罩检测日志分析与可视化

基于ELK的口罩检测日志分析与可视化 1. 引言 在公共场所部署口罩检测系统后&#xff0c;我们面临着一个新的挑战&#xff1a;如何实时监控系统运行状态、快速定位问题、并优化检测性能&#xff1f;传统的日志查看方式已经无法满足需求&#xff0c;我们需要一个能够集中管理、…...

小白也能搞定:CYBER-VISION零号协议智能助盲系统部署全流程

小白也能搞定&#xff1a;CYBER-VISION零号协议智能助盲系统部署全流程 1. 系统介绍与准备工作 CYBER-VISION零号协议是一款专为视障人士设计的智能助盲系统&#xff0c;它通过先进的计算机视觉技术&#xff0c;将周围环境实时转化为可理解的语音提示。想象一下&#xff0c;当…...

Git-RSCLIP入门到精通:从基础地物识别到复杂场景分析全流程解析

Git-RSCLIP入门到精通&#xff1a;从基础地物识别到复杂场景分析全流程解析 1. 遥感智能分析的新利器 在遥感图像分析领域&#xff0c;传统方法往往需要大量标注数据和复杂的模型训练流程。Git-RSCLIP的出现彻底改变了这一局面&#xff0c;它基于先进的SigLIP架构&#xff0c…...

Enhancing LLM Reasoning with Knowledge Graphs: A Faithful and Interpretable Approach

1. 为什么需要知识图谱增强LLM推理 最近两年&#xff0c;大型语言模型&#xff08;LLM&#xff09;的表现确实让人惊艳。我测试过GPT-4在代码生成、文案创作等场景的表现&#xff0c;效果确实超出预期。但当我尝试用LLM做知识密集型任务时&#xff0c;比如回答"贾斯汀比伯…...

Java八股文面试题,堪称2026最强!!!

1、什么是 java 序列化&#xff0c;如何实现 java 序列化 难度系数&#xff1a;⭐ 序列化是一种用来处理对象流的机制&#xff0c;所谓对象流也就是将对象的内容进行流化。可以对流化后的对象进行读写操作&#xff0c;也可将流化后的对象传输于网络之间。序列化是为了解决在…...

手把手教程:在CSDN星图一键部署LFM2.5轻量模型,低配电脑也能跑AI

手把手教程&#xff1a;在CSDN星图一键部署LFM2.5轻量模型&#xff0c;低配电脑也能跑AI 还在为本地跑不动大模型而烦恼吗&#xff1f;今天我要分享一个好消息&#xff1a;即使你的电脑配置不高&#xff0c;也能轻松部署一个实用的AI文本生成模型。LFM2.5-1.2B-Thinking-GGUF就…...

淘宝虚拟商品选品实操:从儿童学习资料到游戏攻略的蓝海挖掘术

淘宝虚拟商品选品高阶指南&#xff1a;从儿童教育到游戏产业的精细化运营策略 在淘宝虚拟商品领域&#xff0c;真正能够持续盈利的卖家往往不是那些追逐热门品类的跟风者&#xff0c;而是懂得在细分市场中寻找差异化机会的"蓝海猎手"。儿童学习资料和游戏攻略这两个看…...

终极英雄联盟工具集:3大核心功能让你轻松掌控游戏全局

终极英雄联盟工具集&#xff1a;3大核心功能让你轻松掌控游戏全局 【免费下载链接】League-Toolkit 兴趣使然的、简单易用的英雄联盟工具集。支持战绩查询、自动秒选等功能。基于 LCU API。 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit League-Toolkit…...