问题描述

在横轴上放了n个相邻的矩形，每个矩形的宽度是1，而第i（1 ≤ i ≤ n）个矩形的高度是h_i。这n个矩形构成了一个直方图。例如，下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3。

请找出能放在给定直方图里面积最大的矩形，它的边要与坐标轴平行。对于上面给出的例子，最大矩形如下图所示的阴影部分，面积是10。

输入格式

第一行包含一个整数n，即矩形的数量(1 ≤ n ≤ 1000)。
　　第二行包含n 个整数h₁, h₂, … , h_n，相邻的数之间由空格分隔。(1 ≤ h_i ≤ 10000)。h_i是第i个矩形的高度。

输出格式

输出一行，包含一个整数，即给定直方图内的最大矩形的面积。

样例输入

6
3 1 6 5 2 3

样例输出

编程语言：Python

解题思想：

1.仔细观察由矩形构成的直方图，最大面积的矩形必然是由矩形的高度决定，单个矩形的面积就是矩形的高度

2.可以模拟对整个直方图每1高度划分一次，从左往右判断每个矩形是否大于等于这个高度

3.如果大于等于则累加当前构成的矩形面积，然后判断该矩形面积是否大于最大矩形面积，如果大于则替换

4.如果不大于等于则不可能出现更大矩形面积，需要把当前构成的矩形面积清空，然后继续往右判断

5.每1高度划分结束后，清空当前构成的矩形面积，以便继续升高高度划分

第一次提交提示超时，当时外层循环是从2遍历到直方图的最大高度，因为题目的高度0<=h<=10000，同时矩形最多有1000个，因此循环次数达到1000W。
改为只循环直方图中出现过的每个高度，拷贝一个矩形高度列表并排序即可实现。

时间复杂度：O(n^2)

IDE代码如下：

NOM = int(input())  # 输入矩形的数量
Height = list(map(int, input().split()))  # 输入每个矩形的高度
CopyHeight = Height[:]  # 拷贝一个矩形高度列表
CopyHeight.sort()
Area = 0  # 默认的面积为矩形的数量
MaxArea = NOM  # 最大矩形面积，初始所有矩形的高度都为1，计算出的结果
 
# 逐渐升高高度进行划分
for i in range(NOM):  # 从小到大遍历直方图中出现过的矩形高度
    for j in range(NOM):  # 从左往右遍历每个矩形的高度
        if Height[j] >= CopyHeight[i]:
            Area += CopyHeight[i]
            if Area > MaxArea:  # 当前构成的矩形面积已经大于之前保存的最大矩形面积
                MaxArea = Area
        else:
            Area = 0
    Area = 0
print(MaxArea)

< >

评论板

共有 7 条评论

fruinly

Also, what was your diet and training like cialis with dapoxetine 2012; 32 4 1009 1130

2023-03-03 07:24 回复
engarma

On SD OCT, loss or thinning of the parafoveal and perifoveal photoreceptor layer and focal disruption of outer segment laminations are consistent with toxicity 13 buy cialis 20mg Results Endometrial cancer was found in 1 318 0

2023-04-28 17:24 回复
jordans for cheap

Read reviews and was a little hesitant since I had already inputted my order. and also but thank god, I had no issues. since the received item in a timely matter, they are in new condition. manner in which so happy I made the purchase. Will be definitely be purchasing again.
jordans for cheap https://www.realcheapjordan.com/

2023-05-16 02:24 回复
cheap jordans for sale

Read reviews and was a little hesitant since I had already inputted my order. also but thank god, I had no issues. just like received item in a timely matter, they are in new condition. anyway so happy I made the purchase. Will be definitely be purchasing again.
cheap jordans for sale https://www.realjordansretro.com/

2023-05-17 01:15 回复
Preliaf

Anaphylactic Reactions And Head And Neck Angioedema buy priligy online

2023-05-31 08:42 回复
Preliaf

5 mg m 2 IV over 30 min on Days 1 5; every 21 d 36, 40 or cialis from india

2023-06-11 11:58 回复
PHLoak

However, it remains unknown whether this risk is related to the hormonal stimulation, the in vitro manipulation of gametes and embryos, or perhaps due to confounding by indication, i where can i buy priligy online safely

2023-07-13 04:09 回复

CCF-CSP_20131203:有趣的矩形