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

目录

  • 1- 思路
    • 题目识别
    • 单调栈
  • 2- 实现
    • 84. 柱状图中最大的矩形——题解思路
  • 3- ACM 实现


  • 原题链接:84. 柱状图中最大的矩形

1- 思路

题目识别

  • 识别1 :给定一个数组 heights ,求解柱状图的最大面积

单调栈

  • 使用 Stack 来实现,遍历数组,存入下标。
  • 本题实现的是一个单调递减栈,目标是找一个以当前为基准,左边第一个比这个小的以及右边第一个比该元素小的元素。

2- 实现

84. 柱状图中最大的矩形——题解思路

在这里插入图片描述

class Solution {public int largestRectangleArea(int[] heights) {int len = heights.length;int[] newH = new int[len+2];int index = 1;for(int i = 0 ; i < len;i++){newH[index++] = heights[i];}heights = newH;len = heights.length;Stack<Integer> st = new Stack<>();int res = 0;st.push(0);// 单调栈for(int i = 0 ; i < len;i++){if(heights[i] >= heights[st.peek()]){st.push(i);}else{while(heights[i] < heights[st.peek()]){int mid = st.peek();st.pop();int left = st.peek();int right = i;int h = heights[mid];int width = right-left-1;res = Math.max(res,h*width);}st.push(i);}}return res;}
}

3- ACM 实现

public class maxArea {public static int maxA(int[] heights){int len = heights.length;int[] newH = new int[len+2];int index = 1;for(int i = 1 ; i < len;i++){newH[index++] = heights[i];}heights = newH;len = heights.length;Stack<Integer> st = new Stack<>();int res = 0;st.push(0);// 单调栈for(int i = 0 ; i < len;i++){if(heights[i] >= heights[st.peek()]){st.push(i);}else{while(heights[i] < heights[st.peek()]){int mid = st.peek();st.pop();int left = st.peek();int right = i;int h = heights[mid];int width = right-left-1;res = Math.max(res,h*width);}st.push(i);}}return res;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String input = sc.nextLine();input = input.replace("[","").replace("]","");String[] parts = input.split(",");int[] nums = new int[parts.length];for(int i = 0 ; i < nums.length;i++){nums[i] = Integer.parseInt(parts[i]);}System.out.println("结果是"+maxA(nums));}
}

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

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

相关文章

wireshark打开时空白|没有接口,卸载重装可以解决

解决方法&#xff1a;卸载wireshark,全选卸载干净&#xff0c;重新安装旧版的wireshark4.2.7, 甚至cmd下运行net start npf时显示服务名无效&#xff0c;但打开wireshark仍有多个接口 错误描述&#xff1a; 一开始下载的是wireshark的最新版&#xff0c;win11 x64 在安装wir…

F28335 时钟及控制系统

1 F28335 系统时钟来源 1.1 振荡器OSC与锁相环PLL 时钟信号对于DSP来说是非常重要的,它为DSP工作提供一个稳定的机器周期从而使系统能够正常运行。时钟系统犹如人的心脏,一旦有问题整个系统就崩溃。DSP 属于数字信号处理器, 它正常工作也必须为其提供时钟信号。那么这个时钟…

几种mfc140u.dll常见错误情况,以及mfc140u.dll文件修复的方法

如果你遇到与mfc140u.dll 文件相关的错误&#xff0c;这通常指的是该mfc140u.dll文件可能丢失、损坏或与您的应用程序不兼容。详细分析关于mfc140u.dll文件错误会对系统有什么影响&#xff0c;mfc140u.dll文件处于什么样的位置&#xff1f;以下是几种常见的错误情况及其修复方法…

Chrome谷歌浏览器登录账号next无反应

文章目录 问题描述 我们的Chrome浏览器在更新之后&#xff0c;会出现登录谷歌账号的时候&#xff0c;当你输入你的谷歌邮箱之后&#xff0c;点击 n e x t next next,也就是下一步的时候&#xff0c;页面没有反应&#xff0c;也就是没有跳转到输入密码的页面。 分析 根据logs里…

vue3 透传 Attributes

前言 Vue 3 现在正式支持了多根节点的组件&#xff0c;也就是片段&#xff01; Vue 2.x 遵循单根节点组件的规则&#xff0c;即一个组件的模板必须有且仅有一个根元素。 为了满足单根节点的要求&#xff0c;开发者会将原本多根节点的内容包裹在一个<div>元素中&#x…

【数据结构】快速排序详解(递归版本)

目录 0. 前言 1. 快速排序的基本思想 2. 快速排序的不同版本的实现 2.1 hoare版本 2.1.1 单趟排序动图演示 2.1.2 递归展开多个子区间进行单趟排序 2.1.3 代码的具体实现 2.1.3.1 霍尔法单趟排序代码 2.3.1.2 霍尔法递归代码 2.2 挖坑法 2.2.1 单趟排序方法动图演示…

【数据结构】图的概念和存储结构

快乐的流畅&#xff1a;个人主页 个人专栏&#xff1a;《C游记》《进击的C》《Linux迷航》 远方有一堆篝火&#xff0c;在为久候之人燃烧&#xff01; 文章目录 引言一、图的概念二、图的存储结构2.1 邻接矩阵2.1.1 成员变量与默认成员函数2.1.2 GetIndex2.1.3 AddEdge2.1.4 Pr…

【设计模式-外观】

这里写自定义目录标题 定义UML图角色作用代码使用场景 定义 为子系统中一组相关接口提供一致界面&#xff0c;定义一个高级接口&#xff0c;使得子系统更加容易使用。 UML图 角色作用 外观&#xff08;Facade&#xff09;角色&#xff1a;这是外观模式的核心&#xff0c;它知…

pdf去水印怎么去掉免费?6个pdf去除水印的方法快码住,超级好用!

pdf去水印怎么去掉免费&#xff1f;您是否有一些带有水印的pdf文档&#xff0c;让您感觉到头疼&#xff1f;您又是否希望能够去除这些水印&#xff0c;或者想用其他水印来替换现有的水印&#xff1f;如果是这样的话&#xff0c;我非常推荐您继续阅读本篇文章。本文将为您提供一…

openeuler 22.03 lts sp4 使用 kubeadm 部署 k8s-v1.28.2 高可用集群

文章目录 [toc]废话篇这篇文章什么时候写的为什么是 openeuler为什么是 22.03 lts sp4高可用架构题外话 干活篇环境介绍系统初始化相关关闭防火墙关闭 selinux关闭 swap开启内核模块开启模块自动加载服务 sysctl 内核参数调整清空 iptables 规则安装各种依赖和工具修改 .bashrc…

Qt --- 信号和信号槽

前言 Linux信号Signal&#xff0c;系统内部的通知机制&#xff0c;进程间通信方式。 信号源&#xff1a;谁发的信号。 信号的类型&#xff1a;哪种类别的信号。 信号的处理方式&#xff1a;注册信号处理函数&#xff0c;在信号被触发的时候自动调用执行。 Qt中的信号和Lin…

JUC学习笔记(三)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 八、共享模型之工具--JUC8.1 AQS 原理1. 概述2 实现不可重入锁自定义同步器自定义锁 3.心得起源目标设计1) state 设计2&#xff09;阻塞恢复设计3&#xff09;队列…

计算机毕业设计选题推荐-共享图书管理系统-小程序/App

✨作者主页&#xff1a;IT研究室✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Python…

【Linux】查看操作系统开机时初始化的驱动模块列表的一个方法

这个方法是摸索出来的&#xff0c;也不一定对&#xff1a; 1、驱动层module_init(module_init_function)作为模块初始化&#xff0c;并且提供模块内部初始化的函数名&#xff1b; 2、找到所有驱动目录drivers下所有module_init(module_init_function)&#xff0c;在内核6.9.0…

你的绩效是不是常年都是B

原创不易&#xff0c;求赞&#xff0c;求关注&#xff0c;&#x1f64f;&#x1f64f;&#x1f64f;&#x1f64f;&#x1f64f;&#x1f64f;&#x1f64f;&#x1f64f; 目录 原创不易&#xff0c;求赞&#xff0c;求关注&#xff0c;&#x1f64f;&#x1f64f;&#x1f64…

http连接github远程仓库密码问题解决办法

目录 一、问题&#xff1a;使用http连接失败 二、解决办法&#xff1a;使用个人访问令牌。 1、生成访问令牌&#xff1a; 步骤 1: 登录 GitHub 步骤 2: 进入设置页面 步骤 3: 生成新的访问令牌 步骤 4: 配置访问令牌 步骤 5: 复制令牌 2. 使用访问令牌 一、问题&#…

图像滤波---各项异性扩散滤波使用笔记及代码

图像滤波---各项异性扩散滤波使用笔记及代码 一、文章内容介绍二、各项异性扩散滤波和各项同性滤波1、各项同性滤波2、各项异性扩散滤波3、各项异性和各项同性的对比 三、各项异性扩散滤波的原理介绍四、各项异性扩散滤波公式五、公式中的参数使用说明1、扩散速率 λ \lambda λ…

kubernetes中pause容器的作用与源码详解

概述 摘要&#xff1a;上一篇文章我们介绍了kubernetes是如何通过pause容器来构建一个pod。本文我们对pause容器做一个总结&#xff0c;并再此基础上次深入浅出&#xff0c;从pause容器的源码详细了解pause容器的实现原理。 正文 pause容器是什么 在 Kubernetes 中&#xff…

STM32(十五):I2C通信

I2C通信 I2C&#xff08;Inter IC Bus&#xff09;是由Philips公司开发的一种通用数据总线&#xff0c;实现单片机读写外部模块寄存器的功能。 两根通信线&#xff1a;SCL&#xff08;Serial Clock&#xff09;、SDA&#xff08;Serial Data&#xff09; 同步&#xff0c;半双工…

css百分比布局中height:100%不起作用

百分比布局时&#xff0c;我们有时候会遇到给高度 height 设置百分比后无效的情况&#xff0c;而宽度设置百分比却是正常的。 当为一个元素的高度设定为百分比高度时&#xff0c;是相对于父元素的高度来计算的。当没有给父元素设置高度&#xff08;height&#xff09;时或设置…