算法leetcode|84. 柱状图中最大的矩形(rust重拳出击)
文章目录
- 84. 柱状图中最大的矩形:
- 样例 1:
- 样例 2:
- 提示:
- 分析:
- 题解:
- rust:
- go:
- c++:
- python:
- java:
84. 柱状图中最大的矩形:
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
样例 1:

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

输入:heights = [2,4]输出: 4
提示:
- 1 <= heights.length <=105
- 0 <= heights[i] <= 104
分析:
- 面对这道算法题目,二当家的再次陷入了沉思。
- 眼睛一看似乎有思路,但是一动手就容易不知如何下手。
- 双循环,遍历每个柱子,查找左边第一个低于自己的柱子,和右边第一个低于自己的柱子,这样就能算出当前柱子这个高度最大的宽度,有搞头,很明显会很慢,还有没有更好的办法呢。
- 找到每个柱子的左右边界(第一个低于自己的柱子)是关键,有没有办法降低查找的复杂度呢?
- 要是能一次遍历就把左右边界找到就好了,祭出神器单调栈,如果栈为空就入栈(这里可以使用技巧,让处理逻辑统一),否则判断下一个柱子如果高于栈顶或者和栈顶一样高也直接入栈,如果低于栈顶就出栈,因为当前这个柱子就是栈顶元素的右边界,重复这个过程,就可以在一次遍历的过程中就找到左右边界。
- 特别要注意遍历过程中栈为空,和遍历完所有柱子但是栈不为空的情况。
题解:
rust:
impl Solution {pub fn largest_rectangle_area(heights: Vec<i32>) -> i32 {let mut ans = 0;let mut stack = vec![-1];let n = heights.len();(0..n).for_each(|i| {while stack.len() > 1 && heights[*stack.last().unwrap() as usize] > heights[i] {// 栈中比当前位置高的那些待确定右边界的下标都可以确定右边界了ans = ans.max(heights[stack.pop().unwrap() as usize] * (i as i32 - 1 - stack.last().unwrap()));}// 入栈,等到能够确定右边界时处理stack.push(i as i32);});while stack.len() > 1 {// 栈中剩余的都是右边没有更低的ans = ans.max(heights[stack.pop().unwrap() as usize] * (n as i32 - 1 - stack.last().unwrap()));}return ans;}
}
go:
func largestRectangleArea(heights []int) int {max := func(x, y int) int {if x > y {return x}return y}ans := 0n := len(heights)stack := []int{-1}for i := 0; i < n; i++ {for len(stack) > 1 && heights[stack[len(stack)-1]] > heights[i] {// 栈中比当前位置高的那些待确定右边界的下标都可以确定右边界了ans = max(ans, heights[stack[len(stack)-1]]*(i-1-stack[len(stack)-2]))// 出栈stack = stack[:len(stack)-1]}// 入栈,等到能够确定右边界时处理stack = append(stack, i)}for len(stack) > 1 {// 栈中剩余的都是右边没有更低的ans = max(ans, heights[stack[len(stack)-1]]*(n-1-stack[len(stack)-2]))// 出栈stack = stack[:len(stack)-1]}return ans
}
c++:
class Solution {
public:int largestRectangleArea(vector<int>& heights) {int ans = 0;const int n = heights.size();stack<int> s;s.push(-1);for (int i = 0; i < n; ++i) {while (s.size() > 1 && heights[s.top()] > heights[i]) {// 栈中比当前位置高的那些待确定右边界的下标都可以确定右边界了int height = heights[s.top()];s.pop();ans = max(ans, height * (i - 1 - s.top()));}// 入栈,等到能够确定右边界时处理s.push(i);}while (s.size() > 1) {// 栈中剩余的都是右边没有更低的int height = heights[s.top()];s.pop();ans = max(ans, height * (n - 1 - s.top()));}return ans;}
};
python:
class Solution:def largestRectangleArea(self, heights: List[int]) -> int:ans = 0n = len(heights)stack = [-1]for i in range(n):while len(stack) > 1 and heights[stack[-1]] > heights[i]:# 比当前位置高的那些待确定右边界的下标都可以确定右边界了ans = max(ans, heights[stack.pop()] * (i - 1 - stack[-1]))# 入栈,等到能够确定右边界时处理stack.append(i)while len(stack) > 1:# 栈中剩余的都是右边没有更低的ans = max(ans, heights[stack.pop()] * (n - 1 - stack[-1]))return ans
java:
class Solution {public int largestRectangleArea(int[] heights) {int ans = 0;final int n = heights.length;Deque<Integer> stack = new LinkedList<>();stack.push(-1);for (int i = 0; i < n; ++i) {while (stack.size() > 1 && heights[stack.peek()] > heights[i]) {// 栈中比当前位置高的那些待确定右边界的下标都可以确定右边界了ans = Math.max(ans, heights[stack.pop()] * (i - 1 - stack.peek()));}// 入栈,等到能够确定右边界时处理stack.push(i);}while (stack.size() > 1) {// 栈中剩余的都是右边没有更低的ans = Math.max(ans, heights[stack.pop()] * (n - 1 - stack.peek()));}return ans;}
}
非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://le-yi.blog.csdn.net/ 博客原创~
相关文章:
算法leetcode|84. 柱状图中最大的矩形(rust重拳出击)
文章目录 84. 柱状图中最大的矩形:样例 1:样例 2:提示: 分析:题解:rust:go:c:python:java: 84. 柱状图中最大的矩形: 给定 n 个非负整…...
Java中通过List中的stream流去匹配相同的字段去赋值,避免for循环去查询数据库进行赋值操作
List<EquipmentDeviceMessage> equipmentDeviceMessageInfo greenThinkTanksInfoPlanMapper.getEquipmentDeviceMessageInfo(phone, startDate, endDate); List<BladeUserVo> userList bladexsqlMapper.getUserList();Q:上面两个列表怎么使用流&#…...
开源酒店预订订房小程序源码系统+多元商户 前端+后端完整搭建教程 可二次开发
大家好啊,罗峰今天来给大家分享一款酒店预订订房小程序源码系统,这款系统进行了全新的升级,从原来的单门店升级成了多门店,可以自由切换账号,统一管理。功能强大。以下是部分代码截图: 酒店预订订房小程序源…...
Leetcode 2906. Construct Product Matrix
Leetcode 2906. Construct Product Matrix 1. 解题思路2. 代码实现 题目链接:2906. Construct Product Matrix 1. 解题思路 这道题其实算是一道数论题。 本来其实python的pow内置函数已经帮我们基本处理了所有的问题了,但是这里稍微做了一点复杂化操…...
【Leetcode Sheet】Weekly Practice 11
Leetcode Test 2731 移动机器人(10.10) 有一些机器人分布在一条无限长的数轴上,他们初始坐标用一个下标从 0 开始的整数数组 nums 表示。当你给机器人下达命令时,它们以每秒钟一单位的速度开始移动。 给你一个字符串 s ,每个字符按顺序分别…...
本地PHP搭建简单Imagewheel私人云图床,在外远程访问
🔥博客主页: 小羊失眠啦 🔖系列专栏: C语言、Linux 🌥️每日语录:追逐影子的人,自己就是影子。 ❤️感谢大家点赞👍收藏⭐评论✍️ 1.前言 云存储在前几年风头无两,云存…...
Python图像处理进阶:Pillow库的中级应用
在上一篇文章中,我们介绍了Python的Pillow库,了解了如何使用Pillow进行一些基础的图像操作。今天,我们将深入探讨Pillow库的中级功能,包括颜色空间转换,直方图,像素操作和绘制。 一、颜色空间转换 在图像…...
多线程怎么共用一个事务
文章目录 场景分析测试对应的其他类我并没有贴出来,因为大家可以自己找个项目走一波测试testSession测试testTransaction 注意使用同一个sqlsession会导致线程安全问题,testSession方法就是在另外线程里面能读取到数据库里面没有的数据.但是有时候业务就是这么奇怪.扩展总结 场…...
scrollIntoView使用与属性详解
scrollIntoView 使用与属性详解 效果图如下图所示 如果要想让元素滚动到指定位置 window.onload function () {containerItems[6].scrollIntoView({ behavior: "smooth" }); };js 代码 const containerItems document.querySelectorAll(".container div&…...
【LeetCode热题100】--169.多数元素
169.多数元素 使用哈希表: class Solution {public int majorityElement(int[] nums) {int n nums.length;int m n/2;Map<Integer,Integer> map new HashMap<>(); //定义一个hashfor(int num:nums){Integer count map.get(num); //Map.get() 方法…...
LeetCode 面试题 10.01. 合并排序的数组
文章目录 一、题目二、C# 题解 一、题目 给定两个排序后的数组 A 和 B,其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法,将 B 合并入 A 并排序。 初始化 A 和 B 的元素数量分别为 m 和 n。 示例: 输入: A [1,2,3,0,0,0], m 3 B [2,5,6], n 3 输…...
揭秘OLED透明拼接屏的参数规格:分辨率、亮度与透明度全解析
作为一种新型的显示技术,OLED透明拼接屏在市场中正在迅速崭露头角,有很多知名品牌厂家能设计、开发、生产高品质的显示产品。 如尼伽、起鸿、康视界、LG、YCTIMES、腾裕等,这些品牌在显示技术领域拥有丰富的经验和声誉,以其卓越的…...
竞赛选题 深度学习YOLOv5车辆颜色识别检测 - python opencv
文章目录 1 前言2 实现效果3 CNN卷积神经网络4 Yolov56 数据集处理及模型训练5 最后 1 前言 🔥 优质竞赛项目系列,今天要分享的是 🚩 **基于深度学习YOLOv5车辆颜色识别检测 ** 该项目较为新颖,适合作为竞赛课题方向࿰…...
linux U盘无法使用,提示“Partition table entries are not in disk order“
问题: U盘在Windows上使用正常,在linux下无法使用fdisk -l 命令提示:Partition table entries are not in disk order $ fdisk -l Disk /dev/sdb: 525 MB, 525336576 bytes 17 heads, 59 sectors/track, 1022 cylinders Units cyl…...
HDLbits: Fsm ps2
本题目理解起来有点难,要观察题目中给的三个时序图,通过时序图可以发现,状态有四个:byte1、byte2、byte3,还有一个“?”状态。其中,byte1的下一个状态一定是byte2,byte2的下一个状态…...
【设计模式】八、桥接模式
文章目录 举例问题分析基本介绍桥接模式在 JDBC 的源码剖析桥接模式的注意事项和细节JDBC 举例 现在对不同手机类型的不同品牌实现操作编程(比如:开机、关机、上网,打电话等), 传统方法对应的类图: 问题分析 扩展性问题(类爆炸)ÿ…...
从零开始的stable diffusion
stable diffusion真的是横空出世,开启了AIGC的元年。不知你是否有和我一样的困惑,这AI工具好像并不是那么听话? 前言 我们该如何才能用好stable diffusion这个工具呢?AI究竟在stable diffusion中承担了什么样的角色?如…...
【Qt之QString】数值与进制字符串间的转换详解
在Qt中,可以使用QString类提供的一些方法来进行数值和进制字符串之间的转换。 以下是示例: 1. 将整数转换为进制字符串: QString类的number静态方法用于将整数转换为字符串表示,并且可以指定转换的进制。方法的定义如下&#x…...
Pytest单元测试框架 —— Pytest+Allure+Jenkins的应用
一、简介 pytestallurejenkins进行接口测试、生成测试报告、结合jenkins进行集成。 pytest是python的一种单元测试框架,与python自带的unittest测试框架类似,但是比unittest框架使用起来更简洁,效率更高 allure-pytest是python的一个第三方…...
科普向丨语音芯片烧录工艺的要求
语音芯片烧录工艺要求烧录精度、速度、内存容量、电源稳定性、兼容性和数据安全性。这些要素需优化和控制以保证生产高效、稳定、安全并烧录出高质量的语音芯片。不同厂家生产的语音芯片在烧录工艺上存在差异,需相应设计和研发以实现兼容。 一、烧录精度 语音芯片烧…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...
ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
初探用uniapp写微信小程序遇到的问题及解决(vue3+ts)
零、关于开发思路 (一)拿到工作任务,先理清楚需求 1.逻辑部分 不放过原型里说的每一句话,有疑惑的部分该问产品/测试/之前的开发就问 2.页面部分(含国际化) 整体看过需要开发页面的原型后,分类一下哪些组件/样式可以复用,直接提取出来使用 (时间充分的前提下,不…...
CentOS 7.9安装Nginx1.24.0时报 checking for LuaJIT 2.x ... not found
Nginx1.24编译时,报LuaJIT2.x错误, configuring additional modules adding module in /www/server/nginx/src/ngx_devel_kit ngx_devel_kit was configured adding module in /www/server/nginx/src/lua_nginx_module checking for LuaJIT 2.x ... not…...
Excel 怎么让透视表以正常Excel表格形式显示
目录 1、创建数据透视表 2、设计 》报表布局 》以表格形式显示 3、设计 》分类汇总 》不显示分类汇总 1、创建数据透视表 2、设计 》报表布局 》以表格形式显示 3、设计 》分类汇总 》不显示分类汇总...
