首页 > 试题广场 >

直方图中的最大矩形

[编程题]直方图中的最大矩形
  • 热度指数：14427 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给出n个数字，代表直方图的条高，直方图每一条的宽度为1，请计算直方图中最大矩形的面积
上图是每条宽度为1, 高度 =[2,1,5,6,2,3].的直方图
图中的阴影部分是该直方图中面积最大的矩形，面积为10个单位
例如：
给出的高度 =[2,1,5,6,2,3],
返回10.

示例1

输入

[2,1,5,6,2,3]

输出

10
算法知识视频讲解
开通博客
头像 予辰
发表于 2020-07-22 11:02:49
题目描述给出n个数字，代表直方图的条高，直方图每一条的宽度为1，请计算直方图中最大矩形的面积。图中的阴影部分是该直方图中面积最大的矩形，面积为10个单位例如：给出的高度 =[2,1,5,6,2,3],返回10.思路分析可以依次遍历数组中的元素，可以知道较小的元素会成为矩形高的限制条件，比如遍历到1时 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 任志启嘉
发表于 2022-12-20 13:55:53
题目描述： 给出n个数字，代表直方图的条高，直方图每一条的宽度为1，请计算直方图中最大矩形的面积。 上图是每条宽度为1, 高度 =[2,1,5,6,2,3]的直方图。 图中的阴影部分是该直方图中面积最大的矩形，面积为10个单位。 例如： 给出的高度 =[2,1,5,6,2,3], 返回10. 输 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 华科不平凡
发表于 2020-09-24 16:26:41
单调栈的最典型用法，下面的代码可以作为单调栈的模版进行记忆： 注意其中第18行在数组最后添加了一个0，这么做可以保证遍历最后一个元素时栈被清空，大大简化了代码 // // Created by jt on 2020/9/24. // #include <vector> #includ 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 一叶浮尘
发表于 2020-04-11 15:52:11
给出n个数字，代表直方图的条高，直方图每一条的宽度为1，请计算直方图中最大矩形的面积 我比较奇怪的是这到题目和栈有什么关系？我用一个o（n*n）的方法做，难道不可以吗？ public class Solution { public int largestRectangleArea(int[ 展开全文
去ta的博客 赞 (0) 回复(1) 收起
头像 立行
发表于 2020-10-15 12:29:37
双指针滑动窗口确定矩形长 以当前高程为基准左右边界水平扩展 遍历小于基准停止扩展，计算矩形图面积，取时大值 func largestRectangleArea( height []int ) int { var max int for i:=0;i<len(height);i 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

栈
难度：
59条回答 16234浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号