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

LeetCode hot 100—柱状图中最大的矩形

news 来源：原创 2025/9/6 0:07:06

题目

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

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

示例

示例 1:

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

示例 2：

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

分析

为了求解柱状图中能够勾勒出的最大矩形面积，我们可以使用单调栈算法来优化计算过程。该算法通过维护一个单调递增的栈来快速找到每个高度左右两侧第一个比它小的高度，从而确定以当前高度为高的最大矩形宽度。

单调栈法

方法思路

单调栈：维护一个存储下标（对应柱状图高度）的栈，栈中的下标对应的高度保持单调递增。

边界处理：在柱状图高度数组末尾添加一个高度为 0 的虚拟元素，确保最后一个元素也能被处理。

遍历计算：对于每个高度，若当前高度小于栈顶高度，则弹出栈顶元素并计算以该高度为高的矩形面积。通过栈中剩余元素确定左右边界，计算宽度并更新最大面积。

时间复杂度：O(n)， n 是数组的长度

空间复杂度：O(n)

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int n = heights.size();vector<int> h = heights;h.push_back(0); // 添加虚拟元素，确保处理最后一个元素stack<int> st; // 存储下标，对应的高度单调递增st.push(-1); // 初始边界下标，避免栈空int maxArea = 0;for (int i = 0; i < h.size(); ++i) {while (st.top() != -1 && h[i] < h[st.top()]) {int top = st.top();st.pop();int width = i - st.top() - 1; // 左右边界之间的宽度maxArea = max(maxArea, h[top] * width);}st.push(i);}return maxArea;}
};

该方法通过单调栈高效地找到每个高度的左右边界，避免了暴力解法中的重复计算，是求解此类问题的最优解法之一。

相关文章：

LeetCode hot 100—柱状图中最大的矩形

题目 给定 n 个非负整数&#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻&#xff0c;且宽度为 1 。 求在该柱状图中&#xff0c;能够勾勒出来的矩形的最大面积。 示例 示例 1: 输入&#xff1a;heights [2,1,5,6,2,3] 输出&#xff1a;10 解释&#xff1a;最…...

编程日记 2025/9/6 0:07:06

从代码学习深度学习 - GRU PyTorch版

文章目录 前言一、GRU模型介绍1.1 GRU的核心机制1.2 GRU的优势1.3 PyTorch中的实现二、数据加载与预处理2.1 代码实现2.2 解析三、GRU模型定义3.1 代码实现3.2 实例化3.3 解析四、训练与预测4.1 代码实现（utils_for_train.py）4.2 在GRU.ipynb中的使用4.3 输出与可视化4.4 解析…...

编程日记 2025/9/2 21:38:53

重要头文件下的函数

1、<cctype> #include<cctype>加入这个头文件就可以调用以下函数&#xff1a; 1、isalpha(x) 判断x是否为字母 isalpha 2、isdigit(x) 判断x是否为数字 isdigit 3、islower(x) 判断x是否为小写字母 islower 4、isupper(x) 判断x是否为大写字母 isupper 5、isa…...

编程日记 2025/8/30 7:02:07

JSON-lib考古现场：在2025年打开赛博古董店的奇妙冒险

各位在代码海洋里捡贝壳的探险家们&#xff01;今天我们要打开一个尘封的Java古董箱——JSON-lib&#xff01;这货可是2003年的老宝贝&#xff0c;比在座很多程序员的工龄还大&#xff01;准备好穿越回Web 1.0时代&#xff0c;感受XML统治时期的余晖了吗&#xff1f; &#x1f…...

编程日记 2025/9/5 0:13:15

实操日志之Windows Server2008R2 IIS7 配置Php7.4.3

Windows7IIS7PHPMySQL - 适用于&#xff08;2008 R2 / 8 / 10&#xff09; 配置需求 操作系统&#xff1a;windows2008IIS版本&#xff1a;7.0 PHP版本&#xff1a;7.4.3 MySQL版本&#xff1a;5.7.12 及以上第一步&#xff1a; 安装 IIS 默认”Internet 信息服务“打勾安…...

编程日记 2025/8/28 22:34:57

Paraformer和SenseVoice模型训练

0.数据准备 如果是训练paraformer模型&#xff0c;我们只需要准备train_wav.scp和train_text.txt以及验证集val_wav.scp和val_text.txt即可。 如果是训练SenseVoice模型&#xff0c;我们需要准备下面几个文件&#xff1a; train_text.txt train_wav.scp train_text_language.…...

编程日记 2025/8/27 18:32:21

Axure数据可视化科技感大屏设计资料——赋能多领域，展示无限价值

可视化大屏如何高效、直观地展示数据&#xff0c;并将其转化为有价值的决策依据&#xff0c;成为了许多企业和组织面临的共同挑战。Axure大屏可视化模板&#xff0c;作为一款强大的数据展示工具&#xff0c;正在以其出色的交互性和可定制性&#xff0c;赋能多个领域&#xff0c…...

编程日记 2025/9/3 3:46:39

C# Winform 入门（7）之简单的抽奖系统邮件

由于比较喜欢英语&#xff0c;这里就把汉字属性名都改成英语了 声明变量&#xff0c;生成随机数 int key 0;Random random new Random(); 窗体加载 private void Form1_Load(object sender, EventArgs e) {timer1.Enabledfalse; } 开始按钮 private void txt_begin_Click(ob…...

编程日记 2025/9/6 3:48:32

scala编程语言

一、抽象类 1、抽象属性和抽象方法 1&#xff09;基本语法 &#xff08;1&#xff09;定义抽象类&#xff1a;abstract class Person{} //通过 abstract 关键字标记抽象类 &#xff08;2&#xff09;定义抽象属性&#xff1a;val|var name:String //一个属性没有初始化&#xf…...

编程日记 2025/9/6 19:05:56

光流 ｜ Farneback、Horn-Schunck、Lucas-Kanade、Lucas-Kanade DoG四种光流算法对比（附matlab源码）

🍅🍅🍅🍅🍅🍅🍅🍅🍅🍅🍅🍅🍅🍅🍅🍅 以下是对四种光流算法的对比分析及MATLAB验证方案，包含原理说明、应用场景和可执行代码🍅🍅🍅🍅🍅🍅🍅🍅🍅🍅🍅🍅🍅 🍓🍓🍓🍓🍍🍍🍍🍍🍍🍍🍍🍍🍍🍍…...

编程日记 2025/9/2 11:36:09

146. LRU 缓存 带TTL的LRU缓存实现(拓展)

LRU缓存 方法一:手动实现双向链表 哈希表 struct Node{int val;int key;Node* prev;Node* next;Node(int a, int b): key(a), val(b), prev(nullptr), next(nullptr) {}Node():key(0), val(0), prev(nullptr), next(nullptr) {} }; class LRUCache { private:Node* removeTai…...

编程日记 2025/9/1 14:28:29

【C++代码整洁之道】第九章 设计模式和习惯用法

文章目录 1. 设计原则与设计模式2. 常见的设计模式及应用场景2.1 单例模式2.2 依赖注入2.3 Adapter模式2.4 Strategy模式2.5 Command模式2.6 Command处理器模式2.7 Composite模式2.8 Observer模式2.9 Factory模式2.10 Facade模式2.11 Money Class模式2.12 特例模式 3. 常见的设…...

编程日记 2025/9/3 3:43:07

【动态规划】混合背包模板

混合背包问题题解 题目传送门&#xff1a;AcWing 7. 混合背包问题 一、题目描述 有 N 种物品和一个容量是 V 的背包。物品分为三类&#xff1a; 01背包&#xff1a;只能用1次&#xff08;si -1&#xff09;完全背包&#xff1a;可以用无限次&#xff08;si 0&#xff09;多…...

编程日记 2025/9/4 20:11:59

Linux 线程1-线程的概念、线程与进程区别、线程的创建、线程的调度机制、线程函数传参

目录 1.线程概念 1.1 线程的核心特点 1.2‌线程的工作模型‌ 1‌.3线程的潜在问题‌ ‌ 1.4 进程和线程区别 1.4.1‌执行与调度‌ ‌ 1.4.2进程和线程区别对比表 1.4.3应用场景‌ ‌ 1.4.4总结 2.线程的创建 2.1验证进程结束后&#xff0c;进程中所有的线程都会强制…...

编程日记 2025/8/29 12:01:17

Python 助力人工智能与机器学习的深度融合

技术革新的 “源动力” 在当今数字化时代&#xff0c;人工智能&#xff08;AI&#xff09;与机器学习&#xff08;ML&#xff09;无疑是最具影响力的技术领域&#xff0c;它们如同强大的引擎&#xff0c;推动着各个行业的变革与发展。Python 凭借其简洁易读的语法、丰富的库和…...

编程日记 2025/9/3 4:33:25

【GPT写代码】动作视频切截图研究器

目录 背景源代码 end 背景 用python写一个windows环境运行的动作视频切截图研究器&#xff0c;用路径浏览的方式指定待处理的视频文件&#xff0c;然后点击分析按钮&#xff0c;再预览区域显示视频预览画面&#xff0c;然后拖动时间轴&#xff0c;可以在预览区域刷新显示相应的…...

编程日记 2025/8/29 15:08:04

从0到神谕：GPT系列的进化狂想曲——用AI之眼见证人类语言的终极形态

开始&#xff1a;语言模型的星际跃迁 在人工智能的浩瀚星海中&#xff0c;GPT系列如同光年加速器&#xff0c;推动人类语言的理解与生成突破维度限制。从2018年GPT-1的初试啼声&#xff0c;到2025年GPT-4o的全模态智慧&#xff0c;这场进化狂想曲不仅是技术的迭代史&#xff0c…...

编程日记 2025/9/2 16:48:47

Go并发编程终极指南：深入内核与工程实践

Go并发编程终极指南&#xff1a;深入内核与工程实践 Go并发编程终极指南&#xff1a;深入内核与工程实践 Go并发编程终极指南&#xff1a;深入内核与工程实践一、Goroutine调度器深度解构1.1 调度器演进史1.2 调度器源码级解析1.3 调度器可视化诊断 二、Channel底层实现揭秘2.1…...

编程日记 2025/8/27 18:31:52

Neo4j操作数据库（Cypher语法）

Neo4j数据库操作语法 使用的数据库版本 (终端查询) >neo4j --version 2025.03.0批量上传数据 UNWIND [{name: Alice, age: 30},{name: Bob, age: 25} ] AS person CREATE (p:Person) SET p.name = person.name, p.age = person.age RETURN p;查询结点总数 MATCH (n) RETU…...

编程日记 2025/9/5 11:21:30

DHCP之中继 Relay-snooping及配置命令

随着网络规模的不断扩大&#xff0c;网络设备不断增多&#xff0c;企业内不同的用户可能分布在不同的网段&#xff0c;一台 DHCP 服务器在正常情况下无法满足多个网段的地址分配需求。如果还需要通过 DHCP 服务器分配 IP 地址&#xff0c;则需要跨网段发送 DHCP 报文 DHCP Rel…...

编程日记 2025/9/2 15:19:06

小迪安全110-tp框架，版本缺陷，不安全写法，路由访问，利用链

入口文件 前端页面显示文件 就是这串代码让我们看到前端的笑脸图 不用入口文件我们要访问这个文件就要按照开发手册的url访问模式 那就是index.php/index/index/index 对应的就是模块&#xff0c;控制器&#xff0c;操作&#xff0c;函数名 如果想要创建新模块&#xff0c;和操…...

编程日记 2025/9/4 6:41:14

Vanna：用检索增强生成（RAG）技术革新自然语言转SQL

引言&#xff1a;为什么我们需要更智能的SQL生成&#xff1f; 在数据驱动的业务环境中&#xff0c;SQL 仍然是数据分析的核心工具。然而&#xff0c;编写正确的 SQL 查询需要专业知识&#xff0c;而大型语言模型&#xff08;LLM&#xff09;直接生成的 SQL 往往存在**幻觉&…...

编程日记 2025/8/31 22:59:09

大语言模型应用和训练（人工智能）

RAG&#xff08;Retrieval Augmented Generation&#xff0c;检索增强生成&#xff09; 定义&#xff1a;是一种将外部知识检索与语言模型生成能力相结合的技术。在传统的大语言模型中&#xff0c;模型的知识是在预训练阶段学到的&#xff0c;可能存在知识过时或不完整的问题。…...

编程日记 2025/9/4 17:44:05

NLP高频面试题（三十五）——LLaMA / ChatGLM / BLOOM的区别

一、LLaMA 训练数据 LLaMA由Meta开发，拥有多个参数规模的版本：7B、13B、33B和65B。其中，较小的7B和13B版本采用了约1万亿tokens进行训练，而更大的33B和65B版本使用了约1.4万亿tokens进行训练。 模型结构特点 LLaMA采用与GPT类似的causal decoder-only Transformer结构，…...

编程日记 2025/9/4 13:24:44

【Python Cookbook】字符串和文本（五）：递归下降分析器

目录 案例 目录 案例 字符串和文本&#xff08;一&#xff09;1.使用多个界定符分割字符串2.字符串开头或结尾匹配3.用 Shell 通配符匹配字符串4.字符串匹配和搜索5.字符串搜索和替换字符串和文本&#xff08;三&#xff09;11.删除字符串中不需要的字符12.审查清理文本字符串1…...

编程日记 2025/9/4 11:47:12

专为 零基础初学者 设计的最简前端学习路线，聚焦核心内容，避免过度扩展，帮你快速入门并建立信心！

第一阶段&#xff1a;HTML CSS&#xff08;2-3周&#xff09; 目标&#xff1a;能写出静态网页&#xff0c;理解盒子模型和布局。 HTML基础 常用标签&#xff1a;<div>, <p>, <img>, <a>, <ul>, <form> 语义化标签&#xff1a;<head…...

编程日记 2025/8/31 13:53:56

大模型-爬虫prompt

爬虫怎么写prompt 以下基于deepseek r1 总结&#xff1a; 以下是为大模型设计的结构化Prompt模板&#xff0c;用于生成专业级网络爬虫Python脚本。此Prompt包含技术约束、反检测策略和数据处理要求&#xff0c;可根据具体需求调整参数&#xff1a; 爬虫脚本生成Prompt模板1 …...

编程日记 2025/9/4 14:30:52

PyTorch深度实践：基于累积最大值的注意力机制设计与性能优化

引言&#xff1a;注意力机制的创新与挑战 在自然语言处理和序列建模中&#xff0c;注意力机制&#xff08;Attention&#xff09;是提升模型性能的关键技术。传统基于 softmax 的注意力机制虽然成熟&#xff0c;但在计算效率和长序列建模中存在局限。本文将介绍一种创新的注意…...

编程日记 2025/9/4 16:03:13

编程bug001：off by one （差一错误）

为什么看似简单的编码错误可能造成大灾难&#xff1f; Off-by-One Error&#xff08;简称OBOE&#xff09;&#xff0c;即由于边界条件处理不当&#xff0c;导致循环、计数或索引时多算一次或少算一次的错误。这是非常常见的编程bug类型&#xff0c;尤其在处理数组、字符串或范…...

编程日记 2025/9/4 0:09:05

JavaScript 中常见的鼠标事件及应用

JavaScript 中常见的鼠标事件及应用 在 JavaScript 中&#xff0c;鼠标事件是用户与网页进行交互的重要方式&#xff0c;通过监听这些事件&#xff0c;开发者可以实现各种交互效果&#xff0c;如点击、悬停、拖动等。 在 JavaScript 中&#xff0c;鼠标事件类型多样&#xff0…...

编程日记 2025/9/1 11:21:50

使用Expo框架开发APP——详细教程

在移动应用开发日益普及的今天&#xff0c;跨平台开发工具越来越受到开发者青睐。Expo 是基于 React Native 的一整套工具和服务&#xff0c;它能够大幅降低原生开发的门槛&#xff0c;让开发者只需关注业务逻辑和界面实现&#xff0c;而不用纠结于复杂的原生配置。本文将从零开…...

编程日记 2025/9/2 5:30:14

深入探究 Hive 中的 MAP 类型：特点、创建与应用

摘要 在大数据处理领域，Hive 作为一个基于 Hadoop 的数据仓库基础设施，提供了方便的数据存储和分析功能。Hive 中的 MAP 类型是一种强大的数据类型，它允许用户以键值对的形式存储和操作数据。本文将深入探讨 Hive 中 MAP 类型的特点，详细介绍如何创建含有 MAP 类型字段的表…...

编程日记 2025/8/31 13:04:34

前端开发工厂模式的优缺点是什么？

一、什么是工厂模式&#xff1f; 工厂模式属于创建型设计模式&#xff0c;核心思想是将对象的实例化过程封装到特定方法或类中&#xff0c;让客户端不需要直接通过new关键字创建对象。 举个例子&#xff1a;就像奶茶店不需要顾客自己调配饮品&#xff0c;而是通过"点单-…...

编程日记 2025/8/30 15:18:01

框架PasteForm实际开发案例，换个口味显示数据，支持echarts，只需要标记几个特性即可在管理端显示(2)

PasteForm框架的主要思想就是对Dto进行标记特性，然后管理端的页面就会以不一样的UI呈现 使用PasteForm框架开发，让你免去开发管理端的烦恼，你只需要专注于业务端和用户端！ 在管理端中，如果说表格是基本的显示方式，那么图表chart就是一个锦上添花的体现！ 如果一个项目拥…...

编程日记 2025/8/28 0:54:46

QEMU学习之路（5）— 从0到1构建Linux系统镜像

QEMU学习之路&#xff08;5&#xff09;— 从0到1构建Linux系统镜像 一、前言 参考&#xff1a;从内核到可启动镜像&#xff1a;0到1构建你的极简Linux系统 二、linux源码获取 安装编译依赖 sudo apt install -y build-essential libncurses-dev flex bison libssl-dev li…...

编程日记 2025/9/5 4:27:37

AI Agent设计模式一：Chain

概念 &#xff1a;线性任务流设计 ✅ 优点&#xff1a;逻辑清晰易调试&#xff0c;适合线性处理流程❌ 缺点&#xff1a;缺乏动态分支能力 from typing import TypedDictfrom langgraph.graph import StateGraph, END# 定义后续用到的一些变量 class CustomState(TypedDict):p…...

编程日记 2025/8/31 15:04:34

实操（进程状态，R/S/D/T/t/X/Z）Linux

1 R 状态并不直接代表进程在运行&#xff0c;而是该进程在运行队列中进行排队&#xff0c;由操作系统在内存维护的队列 #include <stdio.h> #include <unistd.h>int main() {while(1){printf("我在运行吗\n");sleep(1);}return 0; }查看状态&#xff08…...

编程日记 2025/9/4 0:24:54

T-SQL语言的自动化运维

T-SQL语言的自动化运维 引言 在现代IT环境中&#xff0c;自动化运维成为了提高效率、降低成本、提升稳定性的重要手段。数据库作为系统的重要组成部分&#xff0c;运维工作往往需要耗费大量的人力物力。T-SQL&#xff08;Transact-SQL&#xff09;作为Microsoft SQL Server的…...

编程日记 2025/8/30 0:04:28

Day06 分割编译与中断处理

文章目录 1. 例程harib03c&#xff08;c源文件分割并整理makefile文件&#xff09;2. 例程harib03c&#xff08;用于描述段的信息&#xff09;3. 例程harib03d&#xff08;初始化PIC&#xff09;4. 例程harib03e&#xff08;中断处理程序&#xff09; 1. 例程harib03c&#xff…...

编程日记 2025/9/4 18:04:13

数字化三维实训室：无穿戴动作捕捉技术如何赋能体育与舞蹈

在高校体育与舞蹈教学中&#xff0c;精准的动作训练至关重要。传统训练方式依赖教练的肉眼观察与手动记录&#xff0c;存在效率低下、误差较大的情况。尤其在快速连续动作或复杂肢体形态的捕捉中&#xff0c;人工判读易受主观经验限制&#xff0c;难以实现标准化评估。面对传统…...

编程日记 2025/9/5 13:42:30

6. RabbitMQ 死信队列的详细操作编写

6. RabbitMQ 死信队列的详细操作编写 文章目录 6. RabbitMQ 死信队列的详细操作编写1. 死信的概念2. 消息 TTL 过期(触发死信队列)3. 队列超过队列的最大长度(触发死信队列)4. 消息被拒(触发死信队列)5. 最后&#xff1a; 1. 死信的概念 先从概念上解释上搞清楚这个定义&#…...

编程日记 2025/9/3 17:58:47

AI浪潮下，新手短视频制作的破局之道

AI浪潮下&#xff0c;新手短视频制作的破局之道 引言&#xff1a;短视频新时代&#xff0c;AI 带来的机遇与挑战 在当下这个信息飞速流转的时代&#xff0c;短视频已然成为了人们生活中不可或缺的一部分。无论是在通勤路上、午休间隙&#xff0c;还是茶余饭后&#xff0c;打开…...

编程日记 2025/8/27 13:01:04

合肥SMT贴片制造工艺全解析

内容概要 作为电子制造领域的核心工艺&#xff0c;SMT&#xff08;表面贴装技术&#xff09;在合肥地区电子产业链中占据重要地位。本解析以合肥本地化生产场景为基础&#xff0c;系统梳理从焊膏印刷到成品检测的全流程工艺框架。具体而言&#xff0c;制造流程涵盖四大核心阶段…...

编程日记 2025/9/5 19:34:47

ctfshow VIP题目限免 协议头信息泄露

根据提示是协议头信息泄露&#xff0c;那就我们抓个包&#xff0c;抓包才能看到请求体响应体里的协议头啊&#xff0c;抓包之后在响应包里发现了 flag...

编程日记 2025/8/27 21:13:43

【国产工具链发展，生态链分析，TSMaster VS Zcanpro的技术对比】

黎明篇&#xff1a;国产汽车测试工具链的崛起、差距与未来 副标题&#xff1a; 从跟随到超越&#xff0c;中国技术如何重塑全球研发体系 一、国产工具链的崛起逻辑 政策驱动&#xff1a;信创战略与供应链安全需求 国家“十四五”规划明确提出支持关键领域技术自主化&#xff0…...

编程日记 2025/9/6 5:24:36

Linux线程同步与互斥：【线程互斥】【线程同步】【线程池】

目录 一.线程互斥 1.1相关概念 1.2互斥量 为什么会出现负数&#xff1f;&#xff1f; 互斥量的接口 问题&#xff1a; 1.3互斥量实现原理探究 1.4互斥量封装 二.线程同步 2.1条件变量 2.2同步概念与竞态条件 2.3接口 2.4生产者消费者模型 优点 2.5基于BlockingQueue的…...

编程日记 2025/9/3 11:58:30

网络安全基础知识总结

什么是网络安全 采取必要措施&#xff0c;来防范对网络的攻击&#xff0c;侵入&#xff0c;干扰&#xff0c;破坏和非法使用&#xff0c;以及防范一些意外事故&#xff0c;使得网络处于稳定可靠运行的状态&#xff0c;保障网络数据的完整性、保密性、可用性的能力(CIA)。 举例…...

编程日记 2025/9/5 21:25:18

请求被中止: 未能创建 SSL/TLS 安全通道。

需要安装vs2019社区办&#xff0c;下载VisualStudioSetup.exe后&#xff0c;报无法从"https://aka,ms/vs/16/release/channel"下载通道清单错误&#xff0c;接着打开%temp%目录下的最新日志&#xff0c;发现日志里报&#xff1a; [27d4:000f][2025-04-04T21:15:43] …...

编程日记 2025/8/29 9:34:06

FPGA学习（四）——状态机重写LED流水灯并仿真

FPGA学习&#xff08;四&#xff09;——状态机重写LED流水灯并仿真 目录 FPGA学习&#xff08;四&#xff09;——状态机重写LED流水灯并仿真一、状态机编程思想1、状态机要素2、状态迁移图3、状态机写法 二、LED流水灯仿真实现1、代码实现2、modesim仿真 三、实现效果1、仿真…...

编程日记 2025/9/6 0:30:24

spark 集群

hadoop客户端环境准备 找到资料包路径下的Windows依赖文件夹&#xff0c;拷贝hadoop-3.1.0到非中文路径&#xff08;比如d:\hadoop-3.1.0&#xff09; ① 打开环境变量 ② 在下方系统变量中新建HADOOP_HOME环境变量,值就是保存hadoop的目录。 效果如下&#xff1a; ③ 配置P…...

编程日记 2025/9/4 1:26:15