直方图内最大矩形

[编程题]直方图内最大矩形

热度指数：4782 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个数组heights，长度为n，height[i]是在第i点的高度，那么height[i]表示的直方图，能够形成的最大矩形是多少?

1.每个直方图宽度都为1

2.直方图都是相邻的

3.如果不能形成矩形，返回0即可

4.保证返回的结果不会超过2³¹-1

数据范围:

$0 <= heights[i] <= 10^4$

$0 <= heights.length <=10^5$

如输入[3,4,7,8,1,2]，那么如下:

示例1

输入

[3,4,7,8,1,2]

输出

示例2

输入

[1,7,3,2,4,5,8,2,7]

输出

算法知识视频讲解

xqxls

发表于 2022-02-22 22:05:13

题意整理给定一个数组heights，长度为n，height[i]是在第i点的高度。每个height都表示一个直方图，宽度为1。求能组成的最大面积的矩形。方法一（枚举） 1.解题思路思路很简单，就是遍历每一个直方图，将其高度作为矩形的高度，然后分别向前、向后延申，得到可能的矩形的最大长度。展开全文

认认真真coding

发表于 2022-02-23 14:43:58

直方图内最大矩形题目描述给定一个数组heights，长度为n，height[i]是在第i点的高度，那么height[i]表示的直方图，能够形成的最大矩形是多少? 1.每个直方图宽度都为1 2.直方图都是相邻的 3.如果不能形成矩形，返回0即可 4.保证返回的结果不会超过2^31-1 方法一：暴力展开全文

2ez4me

发表于 2022-04-02 21:08:49

import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param heights int整型一维数组展开全文

苏觅云

发表于 2022-05-19 16:42:48

AimerAimer

发表于 2022-02-06 10:45:20

题意：给定一个数组heights，长度为n，height[i]是在第i点的高度，那么height[i]表示的直方图，能够形成的最大矩形是多少? &nb 展开全文

zcr214

发表于 2021-12-09 10:40:44

单调栈一个单调递增的栈，栈内数据形成的矩形面积为最低值（栈首）x总长度但是输入不可能是单调递增的，因此要维持单调性，当后续值无法再入栈时必须将末尾较大的值出栈，直到新的数可以入栈。出栈的数计算其形成的面积（高度x累积的宽度），并把出栈的个数累积为宽度，作为新入栈的数所携带的宽度数据。每次计展开全文

牛客313925129号

发表于 2022-02-22 09:54:40

题意理解一个直方图可以视为多个宽度为1的矩形的紧密相连，每个矩形的高为heights数组中对应的值。这些矩形覆盖了平面上的一个区域，我们要在其中找到一个面积最大的矩形。方法一暴力搜索面积最大的矩形的高一定是heights中的某个值，否则矩形可以增高，从而面积扩大。我们遍历每一个高度，对于he 展开全文