SP1805 HISTOGRA - Largest Rectangle in a Histogram

    • 407通过
    • 1.3K提交
  • 题目来源 SPOJ 1805
  • 评测方式 RemoteJudge
  • 标签
  • 难度 提高+/省选-
  • 时空限制 409ms / 1536MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

      如图所示,在一条水平线上有n个宽为1的矩形,求包含于这些矩形的最大子矩形面积(图中的阴影部分的面积即所求答案)。
    
    输入格式:
    
       有多组测试数据,每组数据占一行。输入零时读入结束。
    
       每行开头为一个数字n(1<=n<=100000),接下来在同一行给出n个数字h1h2...hn(0<=hi<=1000000000)表示每个矩形的高度。
    
    输出格式:
    
       对于每组数据,输出最大子矩阵面积,一组数据输出一行。
    

    题目描述

    A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:

    Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

    输入输出格式

    输入格式:

    输出格式:

    输入输出样例

    暂无测试点
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。