4113: 最大矩形的面积

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：6 解决：6

题目描述

编程实现：

工人砌了一面奇特的砖墙，该墙由N列砖组成（1≤N≤106），且每列砖的数量为Ki（1≤Ki≤104，相邻两列砖之间无缝隙），每块砖的长宽高都为1。

小蓝为了美化这面墙，需要在这面墙中找到一块面积最大的矩形用于涂鸦，那么请你帮助小蓝找出最大矩形，并输出其面积。

例如：N = 6，表示这面墙有6列，每列砖的数量依次为3、2、1、5、6、2，如下图：


图中虚线部分是一块面积最大的矩形，其面积为10。

输入

第一行输入一个正整数N（1≤N≤106），表示这面砖墙由几列砖组成。

第二行输入N个正整数Ki（1≤Ki≤104），表示每列砖的数量，正整数之间以一个空格隔开。

输出

输出一个正整数，表示最大矩形的面积。

样例输入 复制 

6
3 2 1 5 6 2

样例输出 复制 

10

提示

遍历所有砖堆，找出左右两侧第一个高度小于本砖堆的砖堆，就可以算出“高度与本砖堆一致的最大矩形面积”。全部遍历完即可找出最大面积。 

n = int(input())
ls = list(map(int, input().split()))
ls.insert(0,0)  #最左侧增加1个高度为0的虚拟的砖堆，以便编程
ls.append(0)    #最右侧增加1个高度为0的虚拟的砖堆，以便编程
ans=0
for i in range(1,n+1):
    l=i-1
    r=i+1
    while (ls[l]>=ls[i]):
        l-=1
    while (ls[r]>=ls[i]):
        r+=1
    width=r-l-1  #宽度
    area=width*ls[i]  #高度与本砖堆一致的最大矩形面积
    ans=max(ans,area)
print(ans)



来源/分类

提交提交记录统计露一手!